Merge Sort

SplittingMergingSorted run

recursion tree

split downwards, merge back up

831161947

pseudocode

mergeSort(lo, hi)
  if lo >= hi return
  mid = (lo + hi) / 2
  mergeSort(lo, mid); mergeSort(mid+1, hi)
  merge the two halves
  copy merged values back

Frame 1 / 55

Start

unsorted array

Speed4

Custom array

3–16 integers between 1 and 20.