Merge sort is one of the most efficient and popular sorting algorithms. If you are a software developer preparing for your next tech interview, then this one algorithm you must review.

Sorting algorithm questions are a big part of coding interviews at tech companies. In this article, we will help get one step closer to cracking that interview.

We’ll cover:

• What Is Merge Sort?
• How Does It Work?
• Merge Sort Algorithm
• Merge Sort Pseudocode
• Merge Sort Code
• Merge Sort Complexity
• Advantages of Merge Sort
• Disadvantages of Merge Sort
• Merge Sort FAQs

What Is Merge Sort?

Merge sort is a general-purpose comparison-based sorting algorithm — which means that the algorithm compares the elements of the list to sort it. 

Most implementations of this algorithm produce a stable sort, i.e.,, i.e., the order of any two equal elements in the sorted list and the original list stays the same. 

Merge sort has a consistent speed for a given size of data. Therefore, it’s not preferred for sorting an almost sorted array. It works well for sorting linked lists.

How Does It Work?

Merge sort uses the concept of divide and conquer. The problem is divided into multiple subproblems, solved individually, and finally, the result of the subproblems are combined to form the final solution. 

In the case of merge sort, at each step, we divide the list into two smaller sublists until the size of each list reduces to 1. The size of the two sublists is equal when the list is of even length. If the list length is odd, the size of the sublists differs by 1. 

We then sort the sublists and merge them to produce the sorted list.

We may have used a similar technique in real life while sorting a huge number of boxes (or any object). When the number is large, it becomes difficult to sort everything in one go. It’s easier to divide the boxes into smaller chunks, sort those chunks, and then bring the sorted chunks together to get all the boxes in the sorted order.

Merge Sort Algorithm

Step 1: Dividing the List Into Two Smaller Sublists

We divide the list into smaller sublists and make a recursive call to sort the sublists. The recursive call made to sort the sublists divides the sublists into even smaller sublists. 

This process continues until the size of the list reduces to 1.

Step 2: Merging the Sublists to Produce the Sorted List

At this step, we already have our sublists sorted. Now, all we need to do is merge them.

Merging of the lists happens from the bottom to the top. In the figure above, we can see that all the lists in the bottom-most row are of size 1 — these can be considered “sorted,” as they contain just one element.  

Now, we need to sort the lists in the second row from the bottom, and for that, we will merge the already sorted 1-element lists. We first merge the sorted lists of size 1 to produce sorted lists of size 2, then merge the sorted lists of size 2 to create sorted lists of size 4, and so on. 

We stop when we are left with a single list.

Let’s see how we can merge two sorted lists of arbitrary size. The idea is pretty simple and straightforward:

1. Let’s call the two sorted lists A and B 
2. Create an empty list C to hold the elements of the final list
3. At every step, we compare the first element of A and B and select the smaller one
4. Without loss of generality, let’s assume that the first element of A is smaller — we remove this element from A and then append it to C. 
5. We keep repeating this process until one of the lists gets empty
6. We then append the remaining elements of the non-empty list to C

Have a look at the following figure to see this in action:

The merging will repeatedly occur until we get a single list of size n:

Merge Sort Pseudocode

Now that we know how merge sort works, let’s put it in pseudocode. You can use this to create your code in any programming language you like.

function mergesort(arr, start, end)

   if start = end
      return
	  mid = (start + end) / 2

   mergesort(arr, start, mid)
   mergesort(arr, mid + 1, end)

   merge(arr, start, mid, end)

end function


function merge(arr, start, mid, end)

   result :- empty list
   i = start
   j = mid + 1

   while (i <= mid and j <= end)
      if (arr[i] <= arr[j])
         append arr[i] to result
         i = i + 1
      else
         append arr[j] to result         
         j = j + 1
      end if
   end while
   
   while (i <= mid)
      append arr[i] to result
      i = i + 1
   end while
   
   while (j <= end)
      append arr[j] to result
      j = j + 1
	  end while

   i = start
   while(i <= end) 
      arr[i] = first(result)
      i = i + 1
      result = rest(result)
   end while
    
end function

Merge Sort Code 

We’ve used C++ to demonstrate the merge sort code. You don’t need to restrict yourself! Feel free to use this as a reference to code in C, Java, Python, or any programming language of your choice.

// C++ code to demonstrate merge sort algorithm

#include
using namespace std;

void merge(int arr[], int low, int mid, int high) {
    // a vector (dynamic array) to temporarily hold the merged array
    vector result;

    // i points to the first element of 1st subarray
    // j points to the first element of 2nd subarray
    int i = low, j = mid + 1;

    // traversing both subarrays while both are non empty and appending the smaller one to the result
    while(i <= mid && j <= high) {

        // if first unprocessed element (at ith index) of
		
1st subarray is less than or equal to
        // first unprocessed element (at jth index) of 2nd subarray
        if(arr[i] <= arr[j]) {

            result.push_back(arr[i++]);

        } else {

            result.push_back(arr[j++]);

        }

    }

    // appending remaining elements of 1st subarray
    while(i <= mid) {
        result.push_back(arr[i++]);
    }

    // appending remaining elements of 2nd subarray
    while(j <= high) {
        result.push_back(arr[j++]);
    }

    // copying result array to arr[low, high]
    i = low, j = 0;
    while(i <= high) {
        arr[i++] = result[j++];
    }
}

void mergeSort(int arr[], int low, int high) {

    // checking if the size of array is 1
    // if the size is 1 then the array is already sorted
	// and we need not do anything
    if(low == high) {
        return;
    }

    // we need to divide the array into two almost equal halves
    // in case of an odd length array, the size of the halves will differ by 1
    // we divide the array [low, high] into [low, mid] and [mid + 1, high]
    // mid is the midpoint of the range [low, high]
    int mid = (low + high) / 2;

    // recursive call to sort arr[low, mid]
    mergeSort(arr, low, mid);

    // recursive call to sort arr[mid + 1, high]
    mergeSort(arr, mid + 1, high);

    // merging both sorted subarrays arr[low, mid] and arr[mid + 1, high] to form sorted array[low, high]
    merge(arr, low, mid, high);

}

void mergeSort(int arr[], int n) {
    mergeSort(arr, 0, n - 1);
}


int main() {

    int arr[] = {5, 4, 1, 6, 3, 2, 8, 7};

    int n = sizeof(arr) / sizeof(int);
cout << "Array before sorting : \n";
    for(int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << "\n\n";

    mergeSort(arr, n);
    
    cout << "Array after sorting : \n";
    for(int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }

    return 0;
}

‍Output:

Array before sorting : 

5 4 1 6 3 2 8 7

Array after sorting : 

1 2 3 4 5 6 7 8

Merge Sort Complexity

Time Complexity

The time complexity of merge sort is O(n log(n)). This is how it’s calculated:

First, Consider the Number of Rows 

Let’s count the number of rows in the dividing step of the algorithm. We’ll call the number of rows “num_rows” and the size of the list “n”. We keep dividing the list until the size of the list reduces to 1. 

So, n / (2 * 2 * …….. num_rows times) = 1

n = 2 ^ num_rows 

num_rows = log2(n)

num_rows = O(log(n))

Second, Calculate the Time Complexity of Merging Two Lists

The merge algorithm compares the first element of both lists at each step, removes the smaller one from one of the lists, and appends it to the resulting list — after each step, the total size decreases by 1. Therefore:

No. of operations required to empty both lists = sum of sizes of both lists

Third, Calculate the Time Taken to Merge All the Lists in a Row

An important point to note here — each element is present in each row exactly once. This implies that the sum of the size of all the lists in each row is exactly n.

Let’s say there are M lists in any arbitrary row, and the sizes of lists are s1, s2, .., sM.

Time required to merge consecutive pairs of the list in this row

= (s1 + s2) + (s3 + s4) + …… + (s(M-1) + sM)

= sum of the size of all the lists in the row = O(n) 

Finally, Put It All Together

The overall time complexity of merge sort = Time to merge all lists of a row * Number of rows

= sum of the size of all the lists in the row * num_rows

= O(n) * O(log(n))

= O(n log(n))

Recurrence Relation for Calculating Merge Sort Time Complexity 

Let T(n) denote the time to sort a list of size n

T(n) = 2 * T(n / 2) + O(n)

The time required to sort a list of size n is twice the time needed to sort a list of half the size and then merge both the sorted lists in O(n) time.
Solving the above recurrence, we get T(n) = O(n log(n))

Merge sort always takes O(n log(n)) time to sort the list. Even if the list is already sorted, merge sort divides the list into n lists of size 1 and then merges them to get the sorted list of size n.

Space Complexity

The space complexity of merge sort is O(n).

Space complexity only takes into account the auxiliary space we use to solve the problem. Space used to store the input information doesn’t matter here.

We used auxiliary space only for creating a temporary array to hold the result of merged lists. So, the space required is equal to the sum of the size of the lists being merged. 

This, in the worst case, can be equal to n. Hence, the space complexity is O(n).

Advantages of Merge Sort 

• Works well for larger lists
• Has a consistent running time
• Preserves the order of equal elements
• Handles slow-to-access sequential data efficiently

Disadvantages of Merge Sort

• Is slower for smaller lists compared to other sorting algorithms
• Takes up more space
• Requires additional memory for sorting, apart from the given array

Merge Sort FAQs

Question 1: Is merge sort an in-place sorting algorithm?

Answer: An in-place algorithm processes the input and produces the output in the same memory location that contains the input without using any auxiliary space. However, a small extra space for variables is allowed.

And so, merge sort is not an in-place sorting algorithm, because we use an auxiliary array to hold the merged list temporarily.

Question 2: Can we do something smarter and make the algorithm an in-place sort without making the time complexity worse than O(n log(n))? 

Answer: No, we can’t. Here’s why — while merging, we need to read from and write to the same range of the array, and they will overwrite each other. So, we need an auxiliary array.

If we don’t care much about the time complexity, we can make the merge sort algorithm an in-place sort algorithm. The most efficient implementation of an in-place merge sort algorithm takes O(n * log(n)) to merge two lists and overall O(n * log(n) * log(n)) to sort the array.

Question 3: Is merge sort a stable sorting algorithm?

Answer: A sorting algorithm is said to be stable if the order of any two equal elements in the original list and the sorted list stays the same.

It depends on how we implement the algorithm. Most implementations of this algorithm produce a stable sort. While merging the left and the right list, if the first element of both lists are equal, select the element from the left list. This will produce a stable sort. Otherwise, the algorithm will not produce a stable sort.

Are You Ready to Nail Your Next Coding Interview?

If you’re looking for guidance and help with getting started, sign up for our free webinar. As pioneers in the field of technical interview prep, we have trained thousands of software engineers to crack the toughest coding interviews and land jobs at their dream companies, such as Google, Facebook, Apple, Netflix, Amazon, and more!

Sign up now!

----------

Article contributed by Taara Sinh Aatrey