Merge Sort

Stable bottom-up sorting through ordered runs and an auxiliary array

Merge small sorted runs into larger ones

A one-element run is already sorted. Bottom-up Merge Sort first combines neighboring runs of width 1, then width 2, width 4, and so on. Each merge repeatedly takes the smaller front value from two sorted ranges.

Follow the main and auxiliary tracks

Red and blue pointers mark the front of the left and right runs. The lower track is the temporary array: values enter it in sorted order, then the completed range is copied back to the main array. Stable element IDs make that write-back visible without changing the algorithm's meaning.

Input

Set run width to 1; merge adjacent sorted runs of this size.

1function mergeSort(a: number[]): number[] {
const n = a.length;
const temp = new Array(n);
for (let width = 1; width < n; width *= 2) {
  for (let lo = 0; lo < n; lo += 2 * width) {
    const mid = Math.min(lo + width, n);
    const hi = Math.min(lo + 2 * width, n);
    let i = lo, j = mid, k = lo;
    while (i < mid && j < hi) {
      if (a[i] <= a[j]) {
        temp[k++] = a[i++];
      } else {
        temp[k++] = a[j++];
      }
    }
    while (i < mid) temp[k++] = a[i++];
    while (j < hi) temp[k++] = a[j++];
    for (let t = lo; t < hi; t++) a[t] = temp[t];
  }
}
return a;
22}

n10

width1

lo-

mid-

hi-

a[i]-

a[j]-

writeCount0

1 / 78

Predictable performance

Every level processes all n values, and there are log n run widths, so time is O(n log n) in the best, average, and worst cases. This array version uses O(n) auxiliary space and remains stable by taking the left value first on a tie.

Merge invariant: before writing position k, the filled temporary prefix is sorted and contains exactly the smallest values consumed from both runs.

Compare the auxiliary-array tradeoff with in-place Heap Sort.

Algorithm Visualizer

Merge Sort

Merge small sorted runs into larger ones

Follow the main and auxiliary tracks

Predictable performance