Merge Sort Algorithm

3 min readSep 20, 2022

A non in-place sorting algorithm that recursively cuts the array into halves until every subarray has only one element. Then it continuously merges smaller sorted subarrays to a larger one until it builds up a single sorted array. This algorithm runs in O(nlog(n)) time.

Table of Contents· How Does Merge Sort Algorithm Work?
· Graphical Explanation
· Code Implementation
  ∘ Complexity
  ∘ Pseudocode
  ∘ Golang
  ∘ Python

How Does Merge Sort Algorithm Work?

Split…, merge and sort….

Merge sort algorithm keeps splitting the array in half until it reaches a singleton array(base case to stop the recursion). After that, it merges the subarrays in a sorted manner until the whole array is combined to a single sorted array.

This algorithm uses Divide and Conquer strategy to divide an array into subarrays. When the subarray is sorted, it combines the smaller sorted subarrays to a larger one. Finally, the whole array is sorted.

Graphical Explanation

step1: Split the array recursively until it has only one element left.
step2: Merge and sort the subarray recursively until the whole array is sorted.

Code Implementation

Complexity

Time: O(nlog(n))
Space: O(n)
n: the total number of elements in the input array

Pseudocode

mergeSort(array)

# base case
if len(array) <= 1:
   return# find middle index
midIdx = len(array)/2leftSortedArray = mergeSort(array[:midIdx])
rightSortedArray= mergeSort(array[midIdx:])# merge two smaller sorted subarray to a larger sorted array
merge(leftSortedArray, rightSortedArray)

merge(arrayOne, arrayTwo)

merged = []while arrayOne and arrayTwo is not empty:
   # compare the first element, add the smaller one to the merged array
   if arrayOne[0] < arrayTwo[0]:
       append arrayOne[0] to merged array
       remove the front element in the arrayOne
   else:
       append arrayTwo] to merged array
       remove the front element in the arrayTwoappend the rest of elements in arrayOne or arrayTwo to the merged array

Golang

Python

You can access the source code here.

Other sorting algorithms: