Merge Sort

Sorting

avgO(n log n)worstO(n log n)spaceO(n)

main

aux

Allocate an auxiliary buffer of 16 slots

1 / 145

Code

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

procedure mergeSort(A)    ▷ bottom-up  n ← length(A)  aux ← new array of size n  for width ← 1, 2, 4, … while width < n do    for each pair of runs starting at lo do      mid ← lo + width      hi ← min(lo + 2·width, n)      i ← lo; j ← mid      for k ← lo to hi − 1 do        if right run empty or (left not empty and A[i] ≤ A[j]) then aux[k] ← A[i++]        else aux[k] ← A[j++]      end for      copy aux[lo..hi) back into A[lo..hi)    end for  end for  return Aend procedure

Variables

n=16

Counters

comparisons: 0
writes: 0

Size16

Distribution

Custom values2 to 150 whole numbers, each 1 to 999

seed 21

How it works

Bottom-up merge sort: runs of width 1, 2, 4, … are merged pairwise into an auxiliary buffer and copied back, doubling the sorted run length each pass. It is always O(n log n) and stable, but it needs O(n) extra space.

Complexity

Best: O(n log n)
Average: O(n log n)
Worst: O(n log n)
Space: O(n)
Stable: Yes
In place: No

Merge Sort

How it works

Complexity

Search algorithms