Real World Maths Busters

The Maths Behind Everyday Life

The story, the formula and a worked example — see exactly where this maths shows up in the world around you.

Back to all stories
Technology 3 min read

Why Sorting a Million Items Takes Only 20 Million Steps

Efficient sorting is O(n log n), not O(n²).

Bubble sort checks every pair: for 1 million items that’s a trillion comparisons. But merge sort splits and conquers, needing only n × log₂(n) steps.

The n log n Advantage

For n = 1,000,000: n² = 10¹². But n × log₂(n) = 1,000,000 × 20 = 20,000,000. That’s 50,000× fewer steps.

nlog⁡2n vs n2n \log_2 n \text{ vs } n^2

Sorting 1 million items

  1. 1

    Naive (n²)

    (106)2=1012(10^6)^2 = 10^{12}
  2. 2

    Efficient (n log n)

    106×log⁡2(106)≈106×20=2×10710^6 \times \log_2(10^6) \approx 10^6 \times 20 = 2 \times 10^7
  3. 3

    Speedup

    10122×107=50,000×\frac{10^{12}}{2 \times 10^7} = 50{,}000 \times
Answer

50,000× faster with the right algorithm

The takeaway

Algorithm choice matters more than hardware. n log n vs n² is the difference between seconds and days.

Back to all stories