Merge Sort Algorithm

Difficulty: Medium, Asked-in: Microsoft, Amazon, Goldman Sachs, Qualcomm, Bloomberg, Paytm

Introduction to merge sort

Merge sort is a popular sorting algorithm that uses divide and conquer approach to sort an array (or list) of integers (or characters or strings). Here are some excellent reasons to learn merge sort:

One of the fastest sorting algorithms that work in O(nlogn) time complexity.
The best algorithm for sorting linked lists in O(nlogn) time.
An excellent algorithm to learn recursion and problem-solving using divide and conquer approach. We can use similar approach to solve other coding questions.
One of the best algorithms to learn analysis of recursion.
Merging process of merge sort is an excellent idea to learn two-pointers approach. Here both pointers are moving in the same direction to build partial solution. We can use similar approach to solve a lot of other coding questions.

Merge sort divide and conquer idea

Suppose we need to sort an array A[l…r] of n integers starting from index l and ending at index r. The critical question is: Can we solve sorting problem of size n using solution of smaller sub-problems or by applying divide and conquer approach? Let's think!

Divide and conquer steps of merge sort algorithm

If we observe the above diagram, divide and conquer idea looks like this:

Divide part: Divide sorting problem of size n into two different and equal sub-problems of size n/2. We can easily divide the problem by calculating the mid.

Left subproblem: Sorting A[] from l to mid.
Right subproblem: Sorting A[] from mid + 1 to r.

Conquer part: We solve sub-problems recursively and sort both smaller halves. We need not worry about solution to the sub-problems because recursion will do this work for us. Think!

Combine part: We merge both sorted halves to generate the final sorted array. In other words, we combine solution of both sub-problems of size n/2 to solve sorting problems of size n. How? Think!

Merge sort steps

Suppose function mergeSort(int A[], int l, int r) sorts entire array A[] with left and right ends as input parameters.

Divide part: We calculate the mid-index i.e. mid = l + (r - l)/2
Conquer part 1: We call the same function with mid as the right end and recursively sort the left part of size n/2, i.e., mergeSort(A, l, mid).
Conquer part 2: We call the same function with mid + 1 as the left end and recursively sort the right part of size n/2, i.e., mergeSort(A, mid + 1, r).
Combine part: Inside the function mergeSort(), we use function merge(A, l, mid, r) to merge both smaller sorted halves into a final sorted array.
Base case: If we find l == r during recursive calls, then sub-array has one element left, which is trivially sorted. So recursion will not go further and return from here. In other words, the sub-array of size one is the smallest version of sorting problem for which recursion directly returns the solution.

Note: Why are we not calculating mid using the formula (l + r)/2? Explore this excellent google blog to get an answer. Think!

Merge sort pseudocode

void mergeSort(int A[], int l, int r)
{
    if(l >= r)
        return
    int mid = l + (r - l)/2
    mergeSort(A, l, mid)
    mergeSort(A, mid + 1, r)
    merge(A, l, mid, r)
}

Merge sort visualization with example

How merge sort algorithm works?

Implementation of merging algorithm

Solution idea: Two pointers approach

After the conquer step, both left part A[l…mid] and right part A[mid + 1…r] will be sorted. Now we need to combine solution of smaller sub-problems to build solution of the larger problem, i.e., merging both sorted halves to create the larger sorted array. How can we do it? Let's think!

If we store values of both sorted halves into two extra arrays of size n/2 (X[] and Y[]), we can transform the problem into merging sorted arrays X[] and Y[] to the larger sorted array A[]. Using the sorted order property and comparing values one by one, we can build the larger array sorted A[]. How do we implement it? Let's think!

We can use two separate pointers i and j to traverse X[] and Y[] from the start. We compare elements in both arrays one by one and place a smaller value on array A[]. Another way of thinking would be: After each comparison, we add one element to the sorted output to build partially sorted array A[]. One critical question is: Can we merge these two sorted parts in place? Try to do some swapping and comparison operations to get the insight. Think!

Merging algorithm steps

Step 1: Memory allocation and data copy process

We allocate two extra arrays of size equal to the size of left and right sorted parts i.e. size of left sorted part = mid - l + 1, size of right sorted part = r - mid. Note: We include value at mid-index in the left part.
```
int n1 = mid - l + 1
int n2 = r - mid
int X[n1], Y[n2]
```

We copy left and right sorted parts of A[] into extra arrays.

for (int i = 0; i < n1; i = i + 1)
  X[i] = A[l + i]
  
for (int j = 0; j < n2; j = j + 1)
  Y[j] = A[mid + 1 + j]

Step 2: Now we start merging process using two pointers loop.

We initialise pointers i, j, and k to traverse X[], Y[], and A[] i.e. i = 0, j = 0 and k = l. In other words, we start from the first element of both smaller arrays.
Now we run a loop until any smaller arrays reach its end: while(i < n1 && j < n2).
At the first step of iteration, we compare X[0] and Y[0] and place the smallest value at A[0]. Before moving forward to the second iteration, we increment pointer k in A[] and pointer in array containing the smaller value (maybe i or j depending on the comparison). Think!
In similar fashion, we move forward in all three arrays using pointers i, j, and k. At each step, we compare X[i] and Y[j], place smaller value on A[k], and increment k by 1. Based on comparison and position of the smaller value, we also increment pointer i or j. if (X[i] <= Y[j]), we increment i by 1, otherwise we increment j by 1.

Note: This is two-pointer approach of problem-solving where we build partial solution by moving pointers i and j in the same direction.

int i = 0, j = 0, k = l
while (i < n1 && j < n2) 
{
    if (X[i] <= Y[j]) 
    {
        A[k] = X[i]
        i = i + 1
    }
    else 
    {
        A[k] = Y[j]
        j = j + 1
    }
    k = k + 1
}

Merge sort algorithm merging process

Step 3: Loop termination and boundary conditions

Loop will stop when any one of two pointers reaches the end of its array (either i = n1 or j = n2). At this stage, there will be two cases of boundary conditions:

Boundary condition 1: If we exit loop due to condition j = n2, we have reached the end of array Y[] and entirely placed all values of Y[] in A[]. But there may be some values remaining in X[] that still need to be put in the larger array A[]. The idea is: These values are greater than all values available in A[], so we copy remaining values of X[] in the larger array A[]. Think!

while (i < n1) 
{
    A[k] = X[i]
    i = i + 1
    k = k + 1
}

Boundary condition 2: If we exit loop due to condition i = n1, we have reached the end of array X[] and entirely placed all values of X[] in A[]. But there may be some values remaining in Y[] which still need to be put in the larger array A[]. The idea is: These values are greater than all values available in A[], so we copy remaining values of Y[] in the larger array A[]. Think!

while (j < n2) 
{
    A[k] = Y[j]
    j = j + 1
    k = k + 1
}

Merging algorithm pseudocode

void merge(int A[], int l, int mid, int r)
{
    int n1 = mid - l + 1
    int n2 = r - mid
    int X[n1], Y[n2]
    for (int i = 0; i < n1; i = i + 1)
        X[i] = A[l + i]
    for (int j = 0; j < n2; j = j + 1)
        Y[j] = A[mid + 1 + j]

    int i = 0, j = 0, k = l
    while (i < n1 && j < n2) 
    {
        if (X[i] <= Y[j]) 
        {
            A[k] = X[i]
            i = i + 1
        }
        else 
        {
            A[k] = Y[j]
            j = j + 1
        }
        k = k + 1
    }
 
    while (i < n1) 
    {
        A[k] = X[i]
        i = i + 1
        k = k + 1
    }
    while (j < n2) 
    {
        A[k] = Y[j]
        j = j + 1
        k = k + 1
    }
}

Time and space complexity analysis of merging algorithm

This is an excellent code to understand the analysis of iterative algorithm. To understand this better, let's visualize time complexity of each critical step and do the sum to calculate overall time complexity.

Memory allocation process = O(1)
Data copy process = O(n1) + O(n2) = O(n1 + n2) = O(n)
Merging loop in the worst case = O(n1 + n2) = O(n)
Boundary condition 1 in the worst case = O(n1)
Boundary condition 2 in the worst case = O(n2)
Overall time complexity = O(1)+ O(n) + O(n) + O(n1) + O(n2) = O(n)

If we observe closely, merging algorithm time complexity depends on the time complexity of merging loop where comparison, assignment, and increment are critical operations. There could be two different perspectives to understanding this analysis:

Perspective 1: At each step of while loop, we increment either pointer i or j. In other words, we need to access each element of both smaller arrays at least once.
Perspective 2: At each step of iteration, we place one element of smaller sorted arrays to build the larger sorted array A[].

Space complexity = Extra space for storing left part + Extra space for storing right part = O(n1) + O(n2) = O(n1 + n2) = O(n)

Merge sort time complexity analysis

Let's assume that T(n) is the worst-case time complexity of merge sort for n integers. When n > 1 (merge sort on single element takes constant time), we can break down the time complexities as follows:

Divide part: Time complexity of divide part is O(1), because calculating the middle index takes constant time.
Conquer part: We are recursively solving two sub-problems, each of size n/2. So time complexity of each subproblem is T(n/2) and overall time complexity of conquer part is 2T(n/2).
Combine part: As calculated above, the worst-case time complexity of merging process is O(n).

For calculating T(n), we need to add time complexities of the divide, conquer, and combine part.

T(n) = O(1) + 2T(n/2) + O(n) = 2T(n/2) + O(n) = 2T(n/2) + cn

T (n) = c, if n = 1
T(n) = 2 T(n/2) + cn, if n > 1

Note: The merge sort function works correctly when number of elements is not even. To simplify the analysis, we assume that n is a power of 2. This assumption does not affect order of growth in the analysis. Think!

Merge sort analysis using recursion tree method

In this method, we draw recursion tree and count the total number of operations at each level. Finally, we find overall time complexity by doing the sum of operations count at each level.

merge sort time complexity analysis using recursion tree method

As we have seen in the above recursion tree, the cost at each level is O(n), and there is O(logn) number of levels. So time complexity of merge sort = Cost sum at each level = O(logn)*O(n) = O(nlogn).

The best and worst case time complexity will be O(nlogn). The idea is simple: Irrespective of input, merge sort, divide input into equal halves and take O(n) cost at each level. Note: Explore analysis of recursion blog to learn about fundamentals of recursion analysis.

Merge sort analysis using the master theorem

Master method is a direct way to get the solution for recurrences that can be transformed to the type T(n) = aT(n/b) + O(n^k), where a ≥ 1 and b > 1. There are following three cases of the analysis using master theorem:

If f(n) = O(n^k) where k < logb(a) then T(n) = O(n^logb(a))
If f(n) = O(n^k) where k = logb(a) then T(n) = O(n^k * logn)
If f(n) = O(n^k) where k > logb(a) then T(n) = O(n^k)

Let's compare with merge sort recurrence

T(n) = 2 T(n/2) + cn
T(n) = aT(n/b) + O(n^k)

Here a = 2, b = 2 (a > 1 and b > 1)

O(n^k) = cn = O(n¹) => k = 1
Similarly, logb(a) = log 2(2) = 1 = k

It means, merge sort recurrence satisfy the 2nd case of master theorem. Merge sort time complexity T(n) = O(n^k * logn) = O(n^1 * logn) = O(nlogn).

Space complexity analysis of merge sort

Merge sort space complexity depends on the extra space used by the merging process and the size of recursion call stack used by the recursion.

Space complexity of merging process = O(n)
Space complexity for recursion call stack = Height of merge sort recursion tree = O(logn).
Space complexity of merge sort algorithm = O(n) + O(logn) = O(n)

As we have seen here, space complexity is dominated by the extra space used by the merging process.

Important note: We recommend transforming the above pseudo-codes into a favorite programming language (C, C++, Java, Python, etc.) and verifying all test cases. Enjoy programming!

Critical ideas to think about!

Merge sort algorithm is a stable sorting algorithm. That means that identical elements are in same order in the input and output.
For the smaller input size, It is slower in comparison to other sorting algorithms. Even it goes through complete process if array is already or almost sorted.
Merge sort is the best choice for sorting a linked list. Implementing a merge sort in this situation is relatively easy, which requires O(1) extra space. On the other hand, slow random access of linked list elements makes some other algorithms, such as quicksort, perform poorly and others like heap sort completely impossible.
We can parallelize merge sort implementation due to the divide and conquer method, where every smaller sub-problem is independent of each other.
The multiway merge sort algorithm is very scalable through its high parallelization capability, which allows many processors. This makes algorithm a viable candidate for sorting large amounts of data, such as those processed in computer clusters. Also, since memory is usually not a limiting resource in such systems, the disadvantage of space complexity of merge sort is negligible.
Merge sort divide array into 2 equal parts, recursively sorting both smaller halves and finally merging them. Similarly, one of the variations of merge sort is 3-way merge sort, where instead of dividing the array into 2 parts, we divide it into 3 equal parts. Think! The critical question is: what would be the time and space complexity of 3-way merge sort? Is it more efficient than 2-way merge sort?
We can implement merge sort iteratively without using an explicit auxiliary stack. On another side, recursive merge sort uses function call stack to store intermediate values of function parameters l and r and other information. The iterative merge sort works by considering window sizes in exponential oder, i.e., 1, 2, 4, 8...2^n over input array. For each window of any size k, all adjacent pairs of windows are merged into a temporary space, then put back into the array. Explore and Think! We will write a separate blog on this.

Merge Sort: Design, Implementation and Analysis