Begin Algo
Algorithms · 9 lessons

SortingFrom O(n²) to O(n log n)

Sorting is the most-called algorithm there is, and the best material for understanding divide and conquer, stability, and lower-bound proofs. By the end you will know why your language's built-in sort is designed the way it is, and when you can beat n log n.

Why learn Sorting

Where it shows up
Storefronts and leaderboards

Ordering products by price, rating or sales, or a game leaderboard refreshed every minute. Once the data is large, O(n²) versus O(n log n) is the difference between responding and not.

→ Lesson: Merge Sort
ORDER BY and external sorting

A database's ORDER BY is a sorting algorithm; when the data will not fit in memory it uses an external merge sort, reading one chunk at a time.

→ Lesson: Merge Sort
Sorting as a prerequisite

Binary search, deduplication, merging time intervals, finding a median — all assume order. Sort first and the problem after it often becomes easy.

→ Lesson: Sorting Lower Bound
When the values are plain integers

Ages, scores, postcodes — integers over a fixed range can be sorted without comparing at all, which is how counting sort and radix sort get past n log n.

→ Lesson: Counting Sort

Lessons

9 lessons
#AlgorithmDifficulty
01Bubble Sort Bubble sortSwap neighbours — the most obvious and the slowestUsed for: Teaching: understanding adjacent swaps and stability02Selection Sort Selection sortEach pass picks the smallest and puts it in frontUsed for: Fewest writes, for when writing is expensive03Insertion Sort Insertion sortLike sorting a hand of cards; O(n) when nearly sortedUsed for: Small or nearly sorted arrays — built-in sorts switch to it for short runs04Merge Sort Merge sortHalve, sort each, merge. StableUsed for: External sorting of large files, sorting linked lists, counting inversions05Quick Sort QuicksortPick a pivot, split, recurse. Fastest on averageUsed for: The basis of most built-in sorts; Quick Select finds the kth largest06Heap Sort HeapsortHeapify, then extract one at a time. In placeUsed for: When memory is tight and you still need a guaranteed n log n07Counting Sort Counting sortCount how often each value appears — no comparisons at allUsed for: Integers over a small range: scores, ages08Radix / Bucket Sort Radix and bucket sortBucket by digit or by rangeUsed for: Fixed-length integers or strings, such as phone numbers09Sorting Lower Bound The comparison sort lower boundA decision tree proves comparison sorting needs Ω(n log n)Used for: Knowing when faster is impossible