Sorting

Merge Sort (Top-Down)

Split the array recursively, sort each half, then merge two sorted runs into one sorted result.

Algorithm

Basic Implementation

basic.ts 
function mergeSort(values: number[]): number[] {
    if (values.length <= 1) {
        return values;
    }
    const mid: number = Math.floor(values.length / 2);
    const left: number[] = mergeSort(values.slice(0, mid));
    const right: number[] = mergeSort(values.slice(mid));
    const merged: number[] = [];
    let i: number = 0;
    let j: number = 0;
    while (i < left.length && j < right.length) {
        if (left[i] <= right[j]) {
            merged.push(left[i++]);
        } else {
            merged.push(right[j++]);
        }
    }
    return merged.concat(left.slice(i)).concat(right.slice(j));
}

const arr: number[] = [5, 1, 4, 2, 8];
console.log(JSON.stringify(mergeSort(arr)));

The pinned input is [5, 1, 4, 2, 8]. The diagrams show the split into recursive halves, the sorted subarrays, and the final merge choices.

Step 1 - Split the input

The first midpoint splits [5, 1, 4, 2, 8] into left [5, 1] and right [4, 2, 8].

Top-down split used by merge_sort.[5,1,4,2,8]mid = 2[5,1]left[4,2,8]right

Step 2 - Sorted halves return

Recursive calls return [1, 5] and [2, 4, 8] before the final merge begins.

Returned subarrays before the final merge.sidebefore sortafter sortleft[5, 1][1, 5]right[4, 2, 8][2, 4, 8]

Step 3 - Merge by taking smaller fronts

Take 1 from left, then 2 and 4 from right, then the remaining 5 and 8.

Final merge produces [1, 2, 4, 5, 8].choiceleft frontright frontmergedtake 112[1]take 252[1, 2]take 454[1, 2, 4]extend58[1, 2, 4, 5, 8]

Complexity

  • Time: O(n log n)
  • Space: O(n)
  • Stable: yes

Implementation notes

  • TypeScript declares mergeSort(values: number[]): number[], so each call accepts and returns arrays of number values.
  • Base cases return the existing short array reference. Larger calls compute const mid: number = Math.floor(values.length / 2) and allocate copied halves with values.slice(0, mid) and values.slice(mid).
  • Merge state is held in const merged: number[] = [] plus typed cursor bindings let i: number and let j: number.
  • The comparison left[i] <= right[j] uses numeric Number values through TypeScript's number type; taking from left on ties preserves equal-value order.
  • Remaining tails are copied with left.slice(i) and right.slice(j), then joined into the result with concat, so this implementation returns a new sorted array instead of mutating arr.
  • The replay splits [5, 1, 4, 2, 8] into [5, 1] and [4, 2, 8], sorts them to [1, 5] and [2, 4, 8], then prints [1,2,4,5,8] via JSON.stringify(mergeSort(arr)); visible allocation is the input array, copied slice arrays, merge arrays, concat result arrays, and JSON output string.
divide and conquer Each recursive call solves a smaller sorted subproblem.
merge step Two sorted halves are combined by repeatedly taking the smaller front item.