What is merge sort?

You might have heard of many sorting algorithms. In today’s article, we will learn about another exciting and very efficient sorting algorithm called merge sort. You will also learn how to implement it in JS. While discussing the algorithm we will also learn about the concept of recursion and divide and conquer. We will also go in-depth to understand the time and space complexity of merge sort and how it’s better than other sorting algorithms.

Sorting Algorithms

Sorting is a very important concept in computer science. It is used in many applications like searching, database management, etc. There are many sorting algorithms. Some of them are:

• Bubble sort
• Insertion sort
• Selection sort
• Merge sort (the one we will learn today)
• Quick sort
• Heap sort
• Counting sort

There is one pre-requisite to learning merge sort and that is “recursion”. So, before we start learning about merge sort, let’s first learn about recursion (very briefly).

Recursion

Recursion is a method of solving a problem where the solution depends on solutions to smaller instances of the same problem.

A recursive algorithm must have a base case. A recursive algorithm calls itself recursively until it reaches the base case. Then it starts returning the solutions. The solutions to sub-problems are combined to give the solution to the main problem.

For example, we all know how factorial is calculated. It is calculated by multiplying the number by the factorial of the number before it. For example, 5! = 5 * 4!. Similarly, 4! = 4 * 3!. We can keep going on like this until we reach the base case. The base case is 1! = 1. So, we can write the formula for factorial as:

n! = n * (n - 1)!

So, let’s say we have a function that calculates the factorial of a number. Then we can re-write the above formula as:

factorial(n) = n * factorial(n - 1)

We can keep going on like this until we reach the base case. The base case is factorial(1) = 1. So, we can write the formula for factorial as:

factorial(n) = n * factorial(n - 1) // when n > 1
factorial(1) = 1 // when n = 1
Code language: JavaScript (javascript)

So, let’s implement the above formula in JS:

function factorial(n) {
  if (n === 1) {                // base case
    return 1;
  }
  return n * factorial(n - 1); // recursive call
}

console.log(factorial(5));     // will output 120
Code language: JavaScript (javascript)

You can see we are calling the same function inside itself. This is called recursion.

FUN FACT: Search for “recursion” in Google ?

Now, let’s learn about the algorithm.

Merge Sort

Merge sort is a sorting algorithm that uses the divide and conquer strategy. In other words, we break the problem into smaller sub-problems and then solve them. Then we combine the solutions of the sub-problems to get the solution to the main problem.

This breaking of the problem into smaller sub-problems is called “divide” and the combining of the solutions of the sub-problems is called “conquer”. So, the name “divide and conquer”. We also sometimes call the “conquer” step “merge”. Hence it gets the name “merge sort”.

Let’s see how merge sort works. First, we will see how to merge two sorted arrays. Then we will see how to merge and sort an array.

Merging two sorted arrays

Let’s say we have two sorted arrays A and B. We want to merge them into a single sorted array C. We can do this by comparing the first elements of A and B. Whichever is smaller we will first put it in C. And then compare the next elements of A and B. We will keep doing this until we reach the end of either A or B. Then we will put the remaining elements of the other array in C.

Example

Let’s take an example. Assume A = {1, 3, 5, 7} and B = {2, 4, 6, 8}. We want to merge them into C. We will compare the 1st elements of A and B. 1 is smaller than 2. So, we will put 1 in C. Next time we will compare the 2nd element of A i.e 3 with the 1st element of B i.e 2. This time the element  B is smaller, so we will insert that into C. So, now becomes {1, 2}. We will keep doing this until we reach the end of either A or B. So, now A is empty and B is {4, 6, 8}. So, we will insert the remaining elements of B into C. So, now C becomes {1, 2, 4, 6, 8}.

In other words, we will have two-pointers. One for A and one for B. We will compare the elements at the pointers. Whichever is smaller we will insert it into C. And then we will increment the pointer of the array from which we inserted the element. We will keep doing this until we reach the end of either A or B. Then we will insert the remaining elements of the other array into C.

Code

Let’s implement the above algorithm in JS:

function merge(A, B) {
  let C = [];
  let i = 0;
  let j = 0;
  while (i < A.length && j < B.length) {
    if (A[i] < B[j]) {
      C.push(A[i]);
      i++;
    } else {
      C.push(B[j]);
      j++;
    }
  }
  while (i < A.length) {
    C.push(A[i]);
    i++;
  }
  while (j < B.length) {
    C.push(B[j]);
    j++;
  }
  return C;
}

console.log(merge([1, 3, 5], [2, 4, 10])) // will output [1, 2, 3, 4, 5, 10]
Code language: JavaScript (javascript)

Let’s understand the above code.

while (i < A.length && j < B.length) {
  if (A[i] < B[j]) {
    C.push(A[i]);
    i++;
  } else {
    C.push(B[j]);
    j++;
  }
}
Code language: JavaScript (javascript)

In this code section, we are iterating through the arrays A and B. The variable i is a pointer for A and j is a pointer for B. We are comparing the elements at the pointers. Whichever is smaller we are inserting it into C. And then we are incrementing the pointer of the array from which we inserted the element.

while (i < A.length) {
  C.push(A[i]);
  i++;
}

while (j < B.length) {
  C.push(B[j]);
  j++;
}
Code language: JavaScript (javascript)

In this code section, we are inserting the remaining elements of the array into C. We are doing this because we know that the elements of the array are sorted. So, we can just insert the remaining elements  C without comparing them.

What is the time complexity of this merge routine?

The time complexity of this merge routine is O(n + m). We are iterating through the arrays A and B once. So, the time complexity is O(n + m). Here n is the length of A and m the length of B. Remember this, we will need this later.

So, now we know how to merge two sorted arrays. Let’s see how it is used in merge sort.

Overview of Merge Sort

To recall these are the steps of merge sort:

1. Divide the array into two halves.
2. Sort the two halves.
3. Merge the two halves.

At the very first we discussed that merge sort uses recursion. So where does the recursion come into play? It’s in the 2nd step. We have to sort the two halves. So, we can use merge sort to sort the two halves. So, we can write the 2nd step as:

“Sort the two halves using merge sort.”

But we also said that for every recursion we need a base case. So, what is the base case? The base case is when the array has only one element. An array that has only one element is already sorted. So, we can write the 2nd step as:

“Sort the two halves using merge sort. If the array has only one element then it is already sorted.”

Finally, when we have the two sorted halves we can merge them using the algorithm we discussed above. So, we can write the 3rd step as:

“Merge the two sorted halves.”

So, the steps are:

1. Divide the array into two halves.
2. Sort the two halves using merge sort. If the array has only one element then it is already sorted.
3. Merge the two sorted halves.

Merge Sort Implementation in JS

Let’s implement merge sort in JS:

function mergeSort(A) {
  if (A.length === 1) { // base case of the recursion
    return A;
  }

  // STEP 1: divide the array into two subarrays
  let mid = Math.floor(A.length / 2);
  let left = A.slice(0, mid);
  let right = A.slice(mid);

  // STEP 2: sort the two subarrays
  left = mergeSort(left);
  right = mergeSort(right);

  // STEP 3: merge the two sorted subarrays
  return merge(left, right);
}

console.log(mergeSort([5, 4, 3, 2, 1])); // will output [1, 2, 3, 4, 5]
Code language: JavaScript (javascript)

NOTE: We are using the merge function that we implemented above.

Time Complexity of Merge Sort (Master’s Theorem)

We can derive the equation for the time complexity of merge sort using the recurrence relation. Let’s see how.

We start with an array of n items. Let’s say that the time taken to sort the array is T(n). We know that the time taken to sort the array is the sum of the time taken to sort the two halves and the time taken to merge the two halves. We previously derived the time complexity of the merge routine as linear i.e O(n). So, we can write the time taken to sort the array as

We can apply the master theorem to the above equation. The master theorem says that if the recurrence relation is of the form

where a >= 1 b > 1 and f(n) is an asymptotically positive function. And if 

then the time complexity of the algorithm is 

NOTE: There are other conditions for the master theorem. But we are not going to discuss them here.

In our case a = 2, b = 2 and f(n) = O(n). So, we can apply the master theorem to our case, and we get:

So, the time complexity of merge sort is O(logn).

Time Complexity (Recursion Tree)

We can also derive the time complexity using the recursion tree. Since we are splitting the array into two halves at every step, the height of the recursion tree is logn. And at every level of the recursion tree, we merge two arrays of size n/2.effectively making the time complexity of the merge routine O(n).

So, you can think of it as calculating the area of a rectangle. The height of the rectangle is nlogn and the width of the rectangle is O(n). So, the area of the rectangle is O(nlogn).

Space Complexity

The space complexity of merge sort is O(n). We are using an extra array to store the sorted elements. So, the space complexity is O(n).

Conclusion

In this article, we discussed the merge sort algorithm, the steps of merge sort, and how it uses recursion. Further, we also discussed the time complexity of merge sort. Then we derived the time complexity of merge sort using the master theorem and recursion tree. And then we discussed the space complexity of merge sort.

I hope you enjoyed the article. Feel free to connect with me and follow me @ArnabSen1729.