How fast can sorting be?

Complexity analysis Mid-level Python 3.13+ Reviewed 1 Nov 2026 By Best Latest Apps

Predict the output

What does this print?

Python 3.13

import math
for n in (10, 1000):
    need = math.log2(math.factorial(n))
    print(n, round(need), round(n * math.log2(n)))

Options10 22 33 1000 8529 996610 10 33 1000 1000 996610 33 33 1000 9966 9966

Choose an answer, then open Show answer below to check it.

Show answer

Answer: A 10 22 33 1000 8529 9966

Right: log₂(n!) tracks n log₂ n, a little below it.

The lower bound and n log₂ n stay within a constant factor of each other, which is why O(n log n) is optimal for comparison sorts.

Why not the others?

B 10 10 33 1000 1000 9966. log₂(n!) grows faster than n.
C 10 33 33 1000 9966 9966. log₂(n!) is a bit less than n log₂ n.

30-second answer

A comparison sort must tell apart all n! possible orders, and each comparison only has two outcomes, so it needs at least log₂(n!) ≈ n log₂ n comparisons in the worst case. Sorts that do not compare items, such as counting sort and radix sort, can run in O(n + k) when keys are small integers or fixed-length strings.

Practise saying it · 45 s. No recording, just a timer

Explain the sorting lower bound.

Say your answer out loud, then check which of these points you covered:

n! orders
log₂(n!) ≈ n log n
Counting and radix sort escape it

Deep dive

Counting sort: O(n + k) for keys in 0..k-1, stable when done carefully.

Radix sort: O(d·(n + b)) for d digits in base b.

Bucket sort is O(n) on average for evenly spread real numbers.

Common mistakes

Claiming an O(n) general-purpose comparison sort.
Using counting sort when the key range k is huge.

Senior take & follow-ups

Mention the n! argument briefly. It is a neat proof and interviewers enjoy it.

Follow-up questions

Think of your answer first, then open the hint.

Why does stability matter?
Show hint
It lets you sort by one key, then another, and keep earlier order among ties: needed for radix sort.
What is Python's sort on nearly sorted data?
Show hint
Close to O(n), because Timsort finds and merges existing runs.

What each operation costs: Bubble Sort · Merge Sort · Binary Search

From the author

DSA Master - Data & Algorithms

Free on iPhone and iPad: watch 50+ data structures and algorithms step through animations, run the code in the playground, and try the daily challenge.

Get it on the App Store

Suggest a fix if something here is wrong or out of date.