AlgoScope

Merge Sort

Merge two sorted runs by always taking the smaller front value.

Sorting, algorithm, intermediate
Writing 1 into index 0 from the right run.merging 0-11011422384357667write
Writing 1 into index 0 from the right run.merging 0-11011422384357667write

Merge Sort: Eight values

Decision, step 4 of 36

1 is smaller than 5, so 1 is written to index 0.

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

Leads to

Topics that need this one first.

Taught by the same lesson

Merge Sort covers these too, in the same run.