Paul's Python CoursePPC

Merge sort

Not met yet

Merging two sorted piles is quick: compare the two front items, take the smaller, repeat, then tip whatever's left on the end. Merge sort is built from that. Every item starts as a pile of one; neighbouring piles are merged in pairs, round after round, until one pile is left. Each round touches every item once and there are about log n rounds, so it's O(n log n) whatever order the list started in. Take from the left pile on a tie and it's stable.

Try it

main.py

Output

Press Run and what your program prints shows up here.

Easy to get wrong

  • Thinks merge sort needs a round of merging for every item, rather than about log n rounds.
  • Thinks merge sort finishes early when the list is already in order.

Where it comes up