Merge Sort

Concept

Merge Sort is the undisputed king of stable sorting algorithms. It guarantees an absolutely perfect $O(N \log N)$ worst-case time complexity.

It uses the Divide and Conquer paradigm.
If I give you an array of 8 numbers and ask you to sort it, it’s difficult.
If I give you an array of just 1 number, is it sorted? Yes! An array of 1 element is mathematically always perfectly sorted.

Merge Sort relentlessly splits the array in half until every number is isolated in its own array of length 1.
Then, it expertly “Merges” those tiny sorted arrays back together.

The Mechanism

[38, 27, 43, 3, 9, 82, 10]

1. Divide: Split in half recursively until length is 1.

   • [38, 27, 43, 3] and [9, 82, 10]
   • [38, 27], [43, 3], [9, 82], [10]
   • [38], [27], [43], [3], [9], [82], [10]
     (We now have 7 perfectly sorted arrays of length 1).

2. Conquer (Merge): Two sorted arrays can be merged into a single sorted array in perfect $O(N)$ time using two pointers!

   • Merge [38] and [27]. Pointer A vs Pointer B. 27 is smaller. Array becomes [27, 38].
   • Merge [43] and [3] -> [3, 43].
   • Merge [27, 38] and [3, 43]. Pointer A (27) vs Pointer B (3). 3 is smaller! Pick 3. Pointer A (27) vs Pointer B (43). 27 is smaller! Pick 27. Result: [3, 27, 38, 43].
   • The final merge stitches the two massive halves together.

Implementation

// Time Complexity: O(N log N) (Always)
// Space Complexity: O(N) (Not In-Place! Requires arrays for the merges)

function mergeSort(nums: number[]): number[] {
    // 1. BASE CASE: An array of 0 or 1 elements is already perfectly sorted!
    if (nums.length <= 1) return nums;

    // 2. DIVIDE: Find the midpoint and split the array physically in half
    const mid = Math.floor(nums.length / 2);
    
    // slice() creates brand new arrays in memory (causing the O(N) space)
    const leftHalf = nums.slice(0, mid);
    const rightHalf = nums.slice(mid);

    // 3. RECURSE: Tell the children to go sort themselves!
    const sortedLeft = mergeSort(leftHalf);
    const sortedRight = mergeSort(rightHalf);

    // 4. CONQUER: The children returned perfectly sorted arrays. Merge them!
    return merge(sortedLeft, sortedRight);
}

// The O(N) Two-Pointer Merge Helper Function
function merge(left: number[], right: number[]): number[] {
    const result: number[] = [];
    let i = 0; // Pointer for left array
    let j = 0; // Pointer for right array

    // While both arrays still have numbers to compare
    while (i < left.length && j < right.length) {
        if (left[i] <= right[j]) {
            // Left is smaller (or equal). Push it and move pointer.
            // Using <= makes this a STABLE sort!
            result.push(left[i]);
            i++;
        } else {
            // Right is smaller. Push it and move pointer.
            result.push(right[j]);
            j++;
        }
    }

    // One of the arrays is empty! The other array still has numbers left.
    // Because the arrays are sorted, the leftovers are mathematically 
    // larger than everything we just processed. 
    // We just safely dump them onto the end of the result.
    
    while (i < left.length) result.push(left[i++]);
    while (j < right.length) result.push(right[j++]);

    return result;
}

The Fatal Flaw

Merge Sort is mathematically beautiful, but it requires a staggering $O(N)$ Auxiliary Space Complexity.
Look at the nums.slice() and const result: number[] = [] lines. It is physically creating thousands of brand new arrays in RAM as it breaks the problem down and stitches it back together.

If you need to sort an array of 1 Billion integers, Merge Sort requires allocating memory for 1 Billion extra integers in RAM, heavily triggering the Garbage Collector. For massive datasets, Quick Sort (which sorts In-Place using $O(1)$ extra array memory) is highly preferred.

(Note: If you are sorting a Linked List, Merge Sort is the absolute best algorithm in existence, because you can merge linked lists purely by rewiring their .next pointers, achieving $O(N \log N)$ time with perfect $O(1)$ space!)

Interview Questions

Q: In the merge function, why is left[i] <= right[j] so critical?
A: The <= makes Merge Sort a Stable Sort. If we have [25A] in the left half and [25B] in the right half, the <= guarantees that when they tie, the algorithm always blindly prioritizes the element from the Left half. Because the Left half originally appeared earlier in the initial unsorted array, prioritizing it mathematically preserves the original relative order.