Sorting in O(n) time — faster than the comparison barrier. Learn counting sort, radix sort, and bucket sort through stunning animations. No comparisons needed!
// WHAT YOU'LL LEARN
// DEFINITION
Linear sorting refers to sorting algorithms that run in O(n) time — faster than the O(n log n) barrier that limits all comparison-based sorts. They achieve this by not comparing elements at all — instead, they exploit the structure of the data (value range, digits, distribution).
The trade-off: they only work on specific data types. Counting sort needs a small value range. Radix sort needs fixed-width integers. Bucket sort needs uniform distribution. But when the conditions are met, they are dramatically faster than quicksort or merge sort.
// THE 3 LINEAR SORTS
Each linear sort exploits a different property of the data. Pick the one that matches your input.
Count how many times each value appears, then write them out in order. O(n + k). Best when value range k is small.
ANIMATED BELOW ↓📇METHOD 2Sort by each digit, from least significant to most. Uses counting sort as a subroutine. O(d · n). Works on any fixed-width integers.
ANIMATED BELOW ↓🪣METHOD 3Scatter values into n buckets, sort each bucket, then concatenate. O(n) average. Best for uniformly distributed data.
COMPARE BELOW ↓// METHOD 1 · O(n + k)
The simplest linear sort. Count how many times each value appears, compute prefix sums to find positions, then place each value directly. No comparisons — just counting!
You have a stack of ballots, each with a number 0–8. Instead of comparing ballots to each other, you make a tally chart: count how many 0s, how many 1s, how many 2s... Then just write them out in order. No comparisons needed — just counting! That's counting sort.
Press PLAY to start counting sort!
INPUT
COUNT[]
OUTPUT
// HOW IT WORKS — 3 PHASES
Scan the input. For each value, increment count[value]. After this, count[i] = how many times i appears.
Convert counts to positions: count[i] += count[i-1]. Now count[i] = how many values are ≤ i.
Iterate input right-to-left. For each value, decrement count, place at that position. Stable!
When k (the value range) is O(n) — i.e., the range of values is comparable to the number of elements. If k is much larger than n (e.g., sorting 10 numbers with values up to 1 billion), counting sort becomes O(k) which is terrible. That's where radix sort comes in!
// FLOWCHART · ALGORITHM VISUALIZATION
Press PLAY to trace the algorithm through the flowchart.
// PSEUDOCODE · EXECUTION FLOW
Press PLAY to step through the algorithm line by line.
// METHOD 2 · O(d · n)
Sort numbers digit by digit, starting from the least significant (ones place). Each pass uses a stable sort (like counting sort) on one digit. After d passes, the array is fully sorted.
You have cards with numbers like 170, 45, 802. First, sort them by the LAST digit (ones place). Then sort by the tens place. Then hundreds. After each pass, the cards stay in relative order. After all passes — they're fully sorted! That's LSD Radix Sort.
Press PLAY to start radix sort!
ARRAY
// HOW IT WORKS — DIGIT BY DIGIT
Distribute into buckets 0–9 by the last digit. Collect in order.
Distribute by the tens digit. The array stays sorted by ones within each bucket.
Repeat for each digit position. Each pass preserves the order from previous passes.
After d passes (d = number of digits in the max value), the array is fully sorted.
Because we sort by one digit at a time. If a later pass breaks the order established by an earlier pass, the final result is wrong. A stable sort preserves the relative order of elements with the same digit — so the work of previous passes is never undone.
// FLOWCHART · ALGORITHM VISUALIZATION
Press PLAY to trace the algorithm through the flowchart.
// PSEUDOCODE · EXECUTION FLOW
Press PLAY to step through the algorithm line by line.
// TRY IT YOURSELF
Enter your own non-negative integers and sort them with counting sort. See the input, output, and the exact time complexity for your data.
// COMPLEXITY COMPARISON
Drag the slider to change N. See how comparison sorts grow as n log n while linear sorts grow linearly. The gap widens dramatically for large inputs.
merge sort, quicksort, heapsort
k = value range
d = number of digits
For n=1,000: comparison sorts need ~9,966 ops, counting sort needs ~1,100, radix sort needs ~3,000. That's 9× faster with counting sort!
| Algorithm | Best | Average | Worst | Stable? |
|---|---|---|---|---|
| Counting Sort | O(n+k) | O(n+k) | O(n+k) | Yes |
| Radix Sort | O(d·n) | O(d·n) | O(d·n) | Yes (LSD) |
| Bucket Sort | O(n+k) | O(n+k) | O(n²) | Yes |
| Quicksort | O(n log n) | O(n log n) | O(n²) | No |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | Yes |
| Heapsort | O(n log n) | O(n log n) | O(n log n) | No |
// PROPERTIES
Linear sorts don't compare elements to each other. They exploit the structure of the data (digits, value range) to sort directly.
Counting sort is O(n + k). Radix sort is O(d·n). Bucket sort is O(n) average. All beat the O(n log n) comparison-sort barrier — but only under the right conditions.
Counting sort and LSD radix sort are stable — equal elements keep their original relative order. This is crucial when sorting by multiple keys.
They only work on specific data types: non-negative integers with a small range (counting), fixed-width integers (radix), or uniformly distributed values (bucket).
// DID_YOU_KNOW
Harold Seward described counting sort in 1954 for sorting punched cards on early computing machinery — making it one of the oldest sorting algorithms.
In the 1950s–60s, radix sort was the standard sorting method on mainframe computers because it matched how card-sorting machines physically worked.
Any sort that compares elements needs at least Ω(n log n) comparisons. Linear sorts escape this by NOT comparing — they use the data's internal structure instead.
If values range 0–100, counting sort does ~10M + 101 operations. A comparison sort would need ~10M × 23 ≈ 230M. That's 23× slower.
The same digit-by-digit idea extends to characters. Most-recent versions of Java's Arrays.sort() for primitives use dual-pivot quicksort, but for objects use TimSort — a stable hybrid.
If your data is uniformly distributed (like random floats 0–1), bucket sort scatters values into n buckets and sorts each. Average case: O(n). Worst case (all in one bucket): O(n²).
// PRACTICE & ASSESS
Now that you've learned the concept, put it into practice. Solve coding problems and take quizzes to reinforce what you've learned.
// TUTORIAL QUIZZES · LEVELS 1–9
Nine progressive quizzes from Level 1 to Level 9. Each has 10 questions with a 10-minute timer. XP scales with level — L1 gives 10 XP, L9 gives 90 XP. Click a quiz to expand and begin.
// REFERENCES
// READY?
Practice 10,000+ coding problems, follow career roadmaps, and get hired.