Sorting Mind Map

Every sorting visualization on this site on one map. The branches are the main ideas. Each leaf is a page; the grey line under it is the one thing to remember about it. Click a branch to focus on it, click a page to open it.

Recall mode hides the page names. Read the hint, say the name, then click the "?" to check.

1. How the map is organized

Overview of the sorting mind map: Simple sorts, Divide and conquer, Heap sort, Hybrid sorts, Linear time, Compare them, Sorting networks, Selection, Limits of sorting. — The map at a glance: 9 branches, 20 pages.

Ask two questions about a sort and you know which branch it is on:

Does it compare items? If not, it reads the digits or value of each key: that is the linear time branch.
How does it shrink the problem? One item at a time (simple sorts, O(n²)), by splitting in half (divide and conquer), or with a heap (heap sort). Real libraries mix these: the hybrid branch.
Are the compares fixed in advance, whatever the data? Then it is a sorting network, built for GPUs and SIMD.

2. The branches side by side

Branch	Typical time	Extra memory	Stable?
Simple sorts	O(n²), O(n) if nearly sorted (insertion)	O(1)	bubble, insertion: yes
Divide and conquer	O(n log n); quick sort O(n²) worst	merge O(n), quick O(log n)	merge: yes, quick: no
Heap sort	O(n log n) always	O(1)	no
Hybrid	O(n log n), O(n) on runs (TimSort)	TimSort O(n)	TimSort: yes
Linear time	O(n + k)	O(n + k)	counting, radix: yes
Sorting networks	O(log² n) layers, O(n log² n) comparators	O(1), in place	no

3. Five facts to remember

No comparison sort can beat O(n log n) in the worst case.
Insertion sort is the best simple sort, and is fast on small or nearly sorted arrays.
Quick sort is usually the fastest in practice, but a bad pivot makes it O(n²).
Merge sort is stable and always O(n log n), but needs an extra array.
Counting and radix sort are linear only because they look at the key values, not just compare them.

See all sorting pages in the index, or the other mind maps.