Sorting

Four classic ways to put a list in order, side by side.

The idea

Sorting a hand of playing cards shows the big ideas:

Watch it work

Try it

Common mistakes

How fast is it?

Bubble & insertion: O(n²) time (insertion is O(n) on nearly sorted data), O(1) space. Merge sort: O(n log n) always, O(n) extra space. Quick sort: O(n log n) on average, O(n²) worst case, O(log n) stack space.