AlgoScope

Bottom-Up Merge Sort

Merge sort with no recursion, doubling the run width on every pass.

Sorting, algorithm, intermediate
Pass 2 merges neighbouring sorted runs of length 2.merging 6-71051224334856677write
Pass 2 merges neighbouring sorted runs of length 2.merging 6-71051224334856677write

Merge Sort: Eight values

Step, step 15 of 36

Pass 2. Every run of 2 values is now sorted, so merge them in pairs.

Cost

Best
O(n log n)
Average
O(n log n)
Worst
O(n log n)
Space
O(n)

Properties

  • Yes: Comparison based
  • Yes: Stable
  • No: In place
  • No: Adaptive
  • No: Online

A variant of

Taught by the same lesson

Merge Sort covers these too, in the same run.