Core · Module 8
Sorting
The classic sorts, how they move data, and what real standard libraries use.
Sorting is the most studied problem in computing, and every library already solves it well, so this module is less about writing a sort than about understanding the one you call. It covers the simple sorts libraries still use for small pieces, the two O(n log n) workhorses and the trade-offs between them, the sorts that beat the comparison barrier, and the stability guarantees and comparator rules that decide whether a sort does what you meant.
- 1Insertion and selection sortPro — members onlyThe two simplest sorts both take O(n²) steps on scrambled data, but they behave very differently: insertion sort is fast on nearly sorted input and is used inside every major library sort.13 min
- 2Merge sortPro — members onlySplit the array in half, sort each half, merge the two sorted halves. Every level of splitting costs O(n) and there are log n levels, so merge sort is O(n log n) on every input, and it is stable.14 min
- 3Quick sort and partitioningPro — members onlyPartition the array around a pivot so that smaller elements come first, then sort each side. Quick sort is O(n log n) on average, works in place, and with good pivots and a fallback it never hits its O(n²) worst case.15 min
- 4Counting and radix sortPro — members onlyNo sort that only compares elements can beat about n log n comparisons. Counting sort and radix sort don't compare at all: they use the keys as numbers, and sort integers in linear time.14 min
- 5Stability and what libraries usePro — members onlyA stable sort keeps equal elements in their original order, which is what makes sorting by several keys work. Here is which library sorts are stable, what algorithms they really are, and how to write comparators that don't break them.13 min