Merge Sort Algorithm

Merge Sort Walkthrough
🔗
Merge Sort Visualization
🔗
Merge Sort Algorithmic Dance
🔗
Merge Sort (MIT OCW)
🔗
Click here to suggest a better video or view suggestions..

Merge Sort is an efficient algorithm used to order/sort a list of elements in ascending or descending order. It is a type of divide and conquer algorithm: Merge sort algorithm divides the list to be sorted into two halves, recursively sorts each list by using the same algorithm on both the lists and then merges both the sorted lists back into a single sorted list. In short, the entire algorithm can be divided into 3 different stages:

  1. Divide the list into two halves
    • If the list has only 1 element, it means that the list is already sorted. So just return it without dividing
  2. Recursively sort each half (Back to step 1 for each list)
  3. Merge both the halves (Conquer)

The algorithm essentially Divides the list into sub-lists recursively, Conquers sublists (by bringing the size of sublists to 1), Combines them into larger lists until the entire input list is sorted. Below section provides more information about all these stages.

Idea Behind the Algorithm

Understanding Merge Routine

Let’s assume that we have 2 lists with elements in each list ordered in ascending order:

Our goal is to write an algorithm to merge both the lists into a new sorted list (elements in merged list should also be in ascending order).

How can we do it optimally?

Since the elements in new merged list should be in ascending order, we can fill it one by one by taking the least of starting element in both the lists.

The starting element in List-1 is 3 and the starting element in List-2 is 4. So take the smallest of both the elements (3) and add it to the new list. So now the lists look like below:

We do the same thing again, i.e. take the smallest element among the starting element of List-1 (which is 5) and the starting element of List-2 (which is 4). Among 5 and 4, number 4 at the beginning of List-2 is smaller. So we move it from List-2 and to the merged list:

Next, among number 5 at the beginning of List-1 and number 6 at the beginning of List-2, number 5 at the beginning of List-1 is smaller. So we move it from List-1 to the merged list.

We repeat the process again and again until both the lists are empty, and we get the final sorted merged list:

Merge Sort Algorithm

Merge sort algorithm uses the above merging routine by recursively splitting the input array into two halves until only lists with single elements remain. List with one element is a list already sorted. So the algorithm stops dividing when it reaches a list with single element and starts merging lists back into larger sorted lists. Finally when all the divided portions are merged together, a sorted list is what remains. Watch the visualizations below for better understanding.

Let’s assume that the merge sort algorithm is given as input the below list:

The algorithm divides the input list into two equal halves.

We now have two lists that can be merged easily into a single sorted list, if there are sorted independently. So we split each of the lists again into two halves.

We now have four lists and again, they can be merged easily into a single sorted list if all of them are already sorted individually. So each of the four sublists are divided again into two halves.

We now have eight sub lists and this time, the size of each of the sublist is 1. So we can say that all the sublists are already in order. Now we can consider two sublists in groups and merge them together into a single sorted list. There are 8 sublists and after merging 2 sublists in groups, we create 4 sublists of length two and all the four sublists are individually sorted.

We now have four sorted sub lists and so we can merge 2 lists in groups and form 2 sorted sublists from 4 sorted sublists using the merge routine.

We now have just two sorted sublists and so we can merge both the sublists into a single list, which is the final sorted list we require.

Try out the visualization provided below for better understanding of the algorithm.

Visualization of Merge Sort Algorithm

Below is the step by step visualization of merge sort algorithm implemented via recursion:

Implementing Merge Sort Algorithm

Top-down Merge Sort (Recursive) Implementation


# Implementation of MergeSort Algorithm in Python Language


# Function that sorts an array using recursive merge sort implementation
def mergeSort(array):
  if len(array) > 1:

    # m is the index where the array is divided into two subarrays
    m = len(array)//2
    L = array[:m]
    R = array[m:]

    # Sort the two halves by calling mergesort function recursively
    mergeSort(L)
    mergeSort(R)

    # Let us merge both the sorted list together:

    # li - Left index, ri - Right index, mi - Merged Array Index
    li = ri = mi = 0

    # Pick smaller element among the beginning element of Left / Right subarray
    # And place them at the correct position in the merged sorted list
    # Until we include all the element in either Left array or right array
    while li < len(L) and ri < len(R):
      if L[li] < R[ri]:
        array[mi] = L[li]
        li += 1
      else:
        array[mi] = R[ri]
        ri += 1
      mi += 1

    # After we include all the elements in either Left or Right subarray,
    # Include all the remaining elements in either of the subarrays
    while li < len(L):
      array[mi] = L[li]
      li += 1
      mi += 1

    while ri < len(R):
      array[mi] = R[ri]
      ri += 1
      mi += 1


# Let us now try to sort an array using merge sort algorithm
array = [68, 70, 28, 94, 67, 48]

mergeSort(array)

print("Sorted array is: ")
for i in range(len(array)):
  print(array[i], end=" ")

TODO: Bottom-Up Merge Sort (Iterative) Implementation

Characteristics of Merge Sort Algorithm

Time Complexity

An easy way of estimating the time complexity of merge sort algorithm is to think of steps involved in terms of a tree. Since at each level, each list is divided into two, there will be a total of log(N) levels. And at each level, we merge a cumulative of n elements with time complexity of O(N). So the overall time complexity is the sum of time taken for merging lists at all the levels which is equal to logN * O(N) -> O(N logN).

The above analysis is consistent irrespective of the nature of input list. So for all worst, best and average cases, time complexity of merge sort algorithm is O(N logN).

Space Complexity

While merging two divided lists together, we use an auxiliary space equal to the size of both the lists combined. So at peak, we use O(N) space while merging two lists into the final sorted list of length N. The best, worst and average case space complexity of merge sort algorithm is O(N)

Stability

Any sorting algorithm is said to be stable if the relative order of elements with similar id is maintained. For example, if we are given an unordered list of objects [1#, 2%, 1%, 2#], the output has to be [1#, 1%, 2%, 2#]. i.e., the relative order of similar elements has to be maintained.

In this algorithm, we move elements during the merge routine. And if we encounter two identical elements in any two lists currently being merged, we consider the element in first list and add it to the merged list. For example if we encounter element 2% in the first half of list and 2# in the second half of list, we first insert 2% into the merged list and then insert 2#. So the relative order of similar elements is maintained. Hence merge sort is a kind of stable sorting algorithm.

Specializations

Resources & References