Merge Sort Algorithm

I mentioned in yesterday's post that a lot of data manipulation involves lists, nested and otherwise. Another common task is sorting elements in a list. Day 6 of 30 Days of Algorithms is a Merge Sort, which is another "divide-and-conquer" algorithm.

There are many different kinds of sorts but the efficiency of these sorting algorithms vary widely. Even when a sort algorithm is not very efficient, it is a good practice to understand how it works and why it is inefficient. Merge sort is considered to be an efficient sorting algorithm and has a Big-O notation of O(n log n) time complexity, and O(n) space complexity.

How the Algorithm Works

Merge sort is a divide-and-conquer algorithm meaning we break the original list into smaller sub-lists and perform the comparisons on the sub-lists. In the case of merge sort, we recursively split the sub-lists on their mid-point until we end up with a collection of one-item lists. A one-item list is considered sorted.

Each single-item list is compared to another list. The two sub-lists are merged into a single, sorted, two-item list by moving the smaller item to the left, and the larger item to the right. We continuing merging until we are left with a single list that is fully sorted.

Merge Sort Step-by-Step

If there is only a single item, the list is sorted.

Determine the mid-point of the list.

Split the list into left and right halves.

Recursively split-and-merge the two halves.

Continue comparing the current item in each list, pushing the smaller of the two onto the sorted list. As each item is added to the list, the cursor for that list is moved forward.

Return the merged & sorted list.

Merge Sort in JavaScript

This code is also available as a gist on my github repository.

/**
 * Recursively split, sort, and re-merge the array.
 * @param unsortedArray
 * @returns {*[]|*}
 *
 * Big-O:
 *
 * Space complexity : O(n)
 * Time complexity  : O(n Log n)
 */
const mergeSort = (unsortedArray) => {
  /*
   * (1) If there is only one item, it's already sorted :-)
   */

  if (unsortedArray.length <= 1) return unsortedArray;

  /*
   * (2) Determine the mid-point of the dataset to divide & conquer.
   */

  const middle = Math.floor(unsortedArray.length / 2);

  /*
   * (3) Split the array into left & right halves.
   */

  const left = unsortedArray.slice(0, middle),
    right = unsortedArray.slice(middle);

  /*
   * (4) Recursively merge the halves.
   */

  return merge(mergeSort(left), mergeSort(right));
};

/**
 * Merge the two arrays: left and right
 * @param   {array}     left
 * @param   {array}     right
 * @returns {*[]}
 */
const merge = (left, right) => {
  let sorted = [],
    li = 0,
    ri = 0;

  /*
   * (5) Push the smaller of the two items onto the sorted list.
   */

  while (li < left.length && ri < right.length) {
    if (left[li] <code right[ri]) {
      sorted.push(left[li]);
      li++;
    } else {
      sorted.push(right[ri]);
      ri++;
    }
  }

  /*
   * (6) Return the merged, sorted list.
   */
  return sorted.concat(left.slice(li)).concat(right.slice(ri));
};

var numbers = [
  62, 52, 88, 51, 26, 40, 13, 44, 83, 30, 10, 31, 99, 79, 81, 45, 33, 97, 17,
  96, 38, 50, 39, 22, 47, 61, 20, 85, 75, 16, 15, 95, 11, 71, 21, 86, 24, 28,
  46, 5, 89, 54, 70, 87, 35, 42, 69, 82, 84, 76, 60, 98, 77, 68, 8, 66, 96, 78,
  90,
];

console.log(mergeSort(numbers));

You can grab the code from my Github repository for the 30 Days of Algorithms series. Feel free to leave feedback or ask questions in the comments below, or reach me via the Contact Page.