5. Merge Sort Algorithm

This page discusses Merge Sort algorithm using recursion.

We've seen Selection sort using recursion, where the time complexity is o(n²)

We have other sorting algorithms like merge and quick sort which takes lesser time than selection sort. Let's take at merge sort here.

Whenever an array is divided continuously to it's half until a single element is reached, the time complexity of such approach reduces to O(logn) as explained below. Before that, let's take a look at the implementation approach.

Approach

In selection-sort, we process one element(one index place) at a time. This is inefficient due to it's higher time complexity as the way the traversal works adds up o(n) time in each recursive call. The merge sort works on divide and merge method where we divide the array into half and then merge the two halves recursively.

Using merge sort, sort the given array

const arr = [4, 5, 3, 2, 1, 8, 7, 6];
console.log(mergeSort(arr)); //[1, 2, 3, 4, 5, 6, 7, 8]

Recursive Code

const mergeSort = (arr) => {
  if (arr.length <= 1) {
    return arr;
  }

  const mid = Math.floor(arr.length / 2);

  const left = arr.slice(0, mid);
  const right = arr.slice(mid);
  const sortedLeft = mergeSort(left);
  const sortedRight = mergeSort(right);

  return merge(sortedLeft, sortedRight);
};

/* ************************************ */

// Merge function
const merge = (sortedLeft, sortedRight) => {
  let leftPtr = 0,
    rightPtr = 0;
  const merged = [];

  while (leftPtr < sortedLeft.length && rightPtr < sortedRight.length) {
    if (sortedLeft[leftPtr] <= sortedRight[rightPtr]) {
      merged.push(sortedLeft[leftPtr]);
      leftPtr++;
    } else {
      merged.push(sortedRight[rightPtr]);
      rightPtr++;
    }
  }

  while (leftPtr < sortedLeft.length) {
    merged.push(sortedLeft[leftPtr]);
    leftPtr++;
  }

  while (rightPtr < sortedRight.length) {
    merged.push(sortedRight[rightPtr]);
    rightPtr++;
  }

  return merged;
};

Time complexity - O(n logn)

Merge Sort follows the Divide and Conquer approach. I like to call it Divide, Sort, Merge (DSM) because that’s exactly what happens in a bottom-up manner until the entire array is sorted.

At each step, we divide the array into two halves and continue recursively until we reach subarrays of size one. Then, we sort and merge these smaller parts step by step. This process repeats until the entire array is fully sorted and merged.

Dividing the Array into Halves - O(logn)

Since we repeatedly divide the array into halves until we reach individual elements, the number of times we can divide an array of size n is O(log n).

Why is it O(log n)? Let's see

Consider an array of length 8:

[8, 7, 6, 5, 4, 3, 2, 1]

Step 1: Divide into two halves

[8, 7, 6, 5]   [4, 3, 2, 1]

Step 2: Divide further

[8, 7] [6, 5] [4, 3] [2, 1]

Step 3: Divide until single elements remain

[8] [7] [6] [5] [4] [3] [2] [1]

After dividing 3 times, we reach individual elements. Mathematically, this can be written as:

2^3 = 8

which can be generalized as,

2^k = n

where k is the number of times we divide until reaching subarrays of size 1.

Taking logarithm on both sides (base 2):

k = log(base2)n

Thus, the number of divisions required to break an array of size n into individual elements is O(log n). This explains the divide step’s time complexity.

After dividing the array into halves recursively, we need to sort and merge these halves. Let's focus on the sorting and merging steps to understand how they contribute to the overall time complexity.

Sorting and Merging Process

After the array has been divided into subarrays of size 1, we start the merge phase. At each level of recursion, the algorithm merges pairs of subarrays.

1. Merging the Arrays:

• To merge two sorted subarrays, we compare elements from both subarrays and place them in the correct order.

• For each level of recursion, we need to merge the subarrays, and this takes linear time, O(n), where n is the total number of elements across all subarrays at that level.

2. How Many Levels of Merging Are There?

• From the dividing step, we know that we keep halving the array until we reach subarrays of size 1. This process takes O(log n) levels.

• In each level of recursion, all the elements in the array are involved in the merging process.

  • In the first level, we merge the entire array (of size n).

  • In the second level, we merge subarrays of size n/2.

  • In the third level, we merge subarrays of size n/4, and so on.

Total Time Complexity Calculation

Now, let’s combine both the divide and the merge phases:

1. Divide Phase:

• As mentioned earlier, this step involves dividing the array in half, and it takes O(log n) divisions.

Merge Phase:

• At each level of recursion, merging the subarrays requires O(n) time because we have to process each element once.

• Since there are O(log n) levels of recursion, the total time for the merging process across all levels is:

O(n) × O(logn) = O(nlogn)

Thus, the total time complexity of the Merge Sort algorithm is O(n log n).

To Summarize:

• The divide step takes O(log n) time, which is the number of times we split the array.

• The merge step takes O(n) time at each level of recursion, and since we have O(log n) levels, the total time complexity for the merging process is O(n log n).

• Combining both steps, the overall time complexity of Merge Sort is O(n log n).

This makes Merge Sort an efficient algorithm, especially for large datasets, as it runs in O(n log n) time rather than O(n²), which is the time complexity of less efficient algorithms like Bubble Sort or Insertion Sort.

Space complexity - O(n)

1. Recursive Call Stack:

• Since Merge Sort recursively divides the array into halves, the maximum depth of recursion is O(log n) (because the array is divided until single elements remain).

• So, in terms of call stack space, we have O(log n).

2.Additional Array for Merging:

• During the merge step, we create a temporary array to store the sorted elements before copying them back.

• This temporary array requires O(n) space, as it holds all elements before merging them back into the original array.

3. Total Space Complexity Calculation:

• The recursive call stack takes O(log n) space.

• The temporary array takes O(n) space.

• The dominant term here is O(n), so the overall space complexity is:

O(n) + O(logn) = O(n)

• Since O(n) dominates O(log n), we ignore the smaller term and conclude that Merge Sort has O(n) space complexity.

Common Confusions - Why Not O(log n) or O(n log n)?

• Why not O(log n)? → Because we need an extra O(n) array for merging.

• Why not O(n log n)? → We only use O(n) extra space at each level, not at every recursive call.

• Conclusion

  • At any given time, only one side (left or right) is occupying the recursion stack during division process.

  • When left recursion is done, its stack frames are freed before right recursion starts.

  • This is why the max recursion depth is only O(log n), not O(n).