Simple Merge Sort Implementation

This is my merge sort. What is yours?

Simple Merge Sort Implementation

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)
A high-level algorithm of merge sort.

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) {

    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++];
        if (lIndex >= latter.length) {
            arr[i] = former[fIndex++];
        if (former[fIndex] <= latter[lIndex]) {
            arr[i] = former[fIndex++];
        } else {
            arr[i] = latter[lIndex++];


Merge Sort: Counting Inversions | HackerRank
How many shifts will it take to Merge Sort an array?
GitHub Gist: instantly share code, notes, and snippets.