Sorting Algorithms - Merge Sort

Note: This is part of this series of articles on sorting Algorithm

Merge Sort as an efficient sorting algorithm that uses the divide-and-conquer approach (The divide-and-conquer approach entails breaking a problem into sub-problems, solving the sub-problems and then combining the solutions back together to solve the initial problem) to perform sorting on an array. Merge Sort is guaranteed to run in O(nlogn) time (we’ll see how later) which is relatively faster than the average and worst case running times of several other sorting algorithms. There are two steps to mergesort - merging and sorting. We can implement the mergesort algorithm iteratively or recursively (you need to have some knowledge of recursion to understand this approach).

Let’s go over the recursive approach using the divide and conquer technique.

Scenario: Given an array of integers [6, 8, -8, 4, -5, 2, 9], using mergesort, sort and return the array. The sorted array should be in ascending order from left to right.

Approach: We shall take the following steps in sorting this array;

• Declare a base case - if the array has only on element, we want to return the array.
• Divide - We want to split the array into two halves possibly equal in length.
• Conquer - we then use recursion to sort both arrays.
• Combine - after which, we merge the two sorted arrays and return result.

Let’s see what that looks like in code. Note the approach below mutates the original array when doing the merge instead of creating a new result array.

First we create the mergeSort function: The comments in the code explains what each line of code does.

const mergeSort = (array) => {
  // declare the base case
  if (array.length <= 1) return array;
  // find the midpoint of the array
  const mid = Math.floor(array.length / 2);
  // split the array into two halves
  const leftArray = array.slice(0, mid);
  const rightArray = array.slice(mid);
  // recursively split the array passing the left and right arrays to mergeSort
  // until we only have one element left in which case we return
  mergeSort(leftArray);
  mergeSort(rightArray);
  // call the merge function on the array, left array and right array
  return merge(array, leftArray, rightArray);
};

We called the merge function above but we haven’t created that yet. But we know that after splitting the array we need to merge them in sorted order. So my approach is to create a merge function that takes in three arrays, the leftArray, rightArray and the array from which they were split and perform the merge by comparing the element in the firstArray to the secondArray, one after the other while mutating the original array with lesser element. This maintains sorting stability with no need to create another array to push the sorted elements to.

Let’s see what that looks like in code.

const merge = (array, leftArray, rightArray) => {
  // declare pointers to keep track of where we are in each array
  let i = 0; // leftArray pointer
  let j = 0; // rightArray Pointer
  let k = 0; // parent array pointer
  // while we have elements in the leftArray and rightArray
  while (i < leftArray.length && j < rightArray.length) {
    // we compare element in the leftArray to the rightArray
    // we mutate the parent array with the element that is lesser
    // we move our pointers accordingly
    if (leftArray[i] < rightArray[j]) {
      array[k] = leftArray[i];
      i += 1;
    } else {
      array[k] = rightArray[j];
      j += 1;
    }
    k += 1;
  }
  // exiting the while loop there might be elements left in leftArray or rightArray
  // that we haven't compared, we mutate the parent array with these elements.
  while (i < leftArray.length) {
    array[k] = leftArray[i];
    i += 1;
    k += 1;
  }
  while (j < rightArray.length) {
    array[k] = rightArray[j];
    j += 1;
    k += 1;
  }
  // we return the sorted array
  return array;
};

Complexity of Merge Sort

• Dividing the array into two parts takes O(1)
• It takes T(n/2) time to solve each half, therefore solving both halves takes 2T(n/2)
• The merge step takes O(n) time.
• Combining the time according to the Master Theorem gives O(nlogn)
• The time complexity of mergesort is the same, O(nlogn), in best, average and worst case scenario regardless of the number of input. Merge Sort operates on a space complexity of O(n) in worst case.