Why Fast Sorting Matters: n² vs n log n

To sort a playlist of 10 songs, any method is instant. To sort a billion records, the method is everything: an n² algorithm would take years while an n log n one finishes in seconds. Comparing growth rates shows where the gap opens up.

How it works

Growth rates and big-O

In one sentence

Comparison-based sorting needs $\Omega(n\log n)$ comparisons in the worst case, since $\log_2 n! \approx n\log_2 n$ , and merge sort achieves this; simple quadratic sorts make $\Theta(n^2)$ comparisons. On log–log axes, $\Theta(n^k)$ appears as a line of slope $k$ .

General formula

{\htmlData{sym=0}{T_{\text{simple}}(n)}} \approx \frac{{\htmlData{sym=2}{n}}^2}{2}, \qquad {\htmlData{sym=1}{T_{\text{merge}}(n)}} \approx {\htmlData{sym=2}{n}}\log_2 {\htmlData{sym=2}{n}}, \qquad \text{time} = \frac{{\htmlData{sym=3}{T(n)}}}{\htmlData{sym=4}{{v}}}

Doubling n roughly doubles n log n but quadruples n². Repeat that a few dozen times and the gap becomes astronomical.

What the symbols mean

$T_{\text{simple}}(n)$
Simple sort
Comparisons a pairwise method like selection sort makes.
$T_{\text{merge}}(n)$
Merge sort
Comparisons merge sort makes.
$n$
Items
How many items are sorted.
$T(n)$
Comparisons
Work the algorithm does on n items.
$v$
Speed
Comparisons the computer makes per second.

Simple sorts like selection or insertion sort compare items in pairs: about n²/2 comparisons for n items.
Merge sort and its relatives split the work in half again and again: about n log₂ n comparisons.
On log-scale axes the growth rates become straight lines with slopes 2 and just over 1. The gap between them grows without limit: at a billion items it's a factor of about 17 million.
A faster computer shifts every line down by the same amount but can't change the slopes. Better algorithms beat better hardware.

Learn the math

Growth of Functions and Big-ODiscrete · Lesson 43, Algorithms and Complexity Analyzing Algorithms: Searching and SortingDiscrete · Lesson 44, Algorithms and Complexity