The high-level algorithm of merge sort is concise and beautiful. Merge sort is the king of sorting algorithms because of its simplicity and great stability.

MergeSort(array, start, end):
  if start < end:
    mid = Floor((start + end)/2)
    MergeSort(array, start, mid)
    MergeSort(array, mid+1, end)
    Merge(array, start, end)

However, when it comes to implementing it in a programming language, you need to make design decisions for the lower level part. I have written a simple and clean merge sort in JavaScript whose space complexity is O(n log(n)). Unless you are harshly constrained on the memory resource. this algorithm will do.

The Point of the Implementation

The implementation shown below copies the former and the latter halves of the original array first. Next, it performs merge sort on both arrays, and then it merges on the original array. As a result, we can avoid the complication of the merge algorithm.

function mergeSort(arr) {
    /// Observation
    // - Make copies of the former and the latter half of the array
    // - Call mergeSort() on each copy
    // - Merge them on arr
    const n = arr.length;
    if (n <= 1) {
        return;
    }

    const mid = Math.floor(n/2);
    const former = mergeSort(arr.slice(0, mid));
    const latter = mergeSort(arr.slice(mid, n));
    
    let [fIndex, lIndex] = [0, 0];
    for(let i = 0; i < n; i++) {
        if (fIndex >= former.length) {
            arr[i] = latter[lIndex++];
            continue;
        }
        if (lIndex >= latter.length) {
            arr[i] = former[fIndex++];
            continue;
        }
        if (former[fIndex] <= latter[lIndex]) {
            arr[i] = former[fIndex++];
        } else {
            arr[i] = latter[lIndex++];
        }
    }
}

Reference

Merge Sort: Counting Inversions | HackerRank

How many shifts will it take to Merge Sort an array?

HackerRank

MergeSort.js

GitHub Gist: instantly share code, notes, and snippets.

Gist262588213843476