Counting sort
A non-comparison sorting algorithm for integers in fixed range, achieving O(n + k) time where k is range. Counting sort is faster than comparison sorts for small integer ranges. Not comparison-based, avoiding O(n log n) lower bound.
Formula
Time: O(n + k) where k is the range of values
Real World
When the UK's UCAS system sorts hundreds of thousands of applicants by their A-level point scores (a small fixed range of 0–168), counting sort processes them far faster than comparison-based alternatives.
Exam Focus
Emphasise counting sort is not comparison-based; clearly state why it breaks the O(n log n) lower bound.
How well did you know this?