Linear Time Sorting

The previous article proved that comparison-based sorting cannot beat O(n log n). But what if we don't use comparisons? This article explores three algorithms that achieve O(n) time by exploiting properties of the data: Counting Sort, Radix Sort, and Bucket Sort.

These algorithms aren't always applicable, but when they are, they can be orders of magnitude faster than QuickSort or MergeSort - especially for large datasets with bounded integer keys.

📋 At a Glance

Where k = range of values, d = number of digits

🎯 What You'll Learn

After reading this article, you will be able to:

• Implement Counting Sort for integers with known range
• Apply Radix Sort to sort millions of integers faster than QuickSort
• Use Bucket Sort for uniformly distributed floating-point numbers
• Know when O(n) sorts beat O(n log n) in practice
• Combine these algorithms with comparison sorts for hybrid approaches
• Avoid common pitfalls like negative numbers and memory overhead

🔥 Production Story: 100 Million Log Entries

A monitoring system needed to sort 100 million log entries by timestamp for daily analysis. The timestamp was a Unix epoch in milliseconds, ranging from midnight to midnight (86,400,000 values).

JAVA(5 lines)
Code
Loading syntax highlighter...

• Timestamps were bounded (one day = 86.4M milliseconds)
• Timestamps were dense (many entries per millisecond)
• MergeSort was doing ~1.7 billion comparisons

JAVA(25 lines)
Code
Loading syntax highlighter...

JAVA(8 lines)
Code
Loading syntax highlighter...

🧠 Mental Model: Trading Assumptions for Speed

Linear time sorts work by avoiding comparisons entirely. Instead, they use direct addressing or arithmetic:

TEXT(27 lines)
Code
Loading syntax highlighter...

TEXT(6 lines)
Code
Loading syntax highlighter...

🔬 Deep Dive

1. Counting Sort: The Foundation

Counting Sort works by counting occurrences of each value, then using those counts to place elements directly.

JAVA(21 lines)
Code
Loading syntax highlighter...

JAVA(27 lines)
Code
Loading syntax highlighter...

TEXT(10 lines)
Code
Loading syntax highlighter...

JAVA(21 lines)
Code
Loading syntax highlighter...

2. Radix Sort: Sorting by Digits

Radix Sort sorts numbers digit by digit, using a stable sort (usually Counting Sort) for each digit.

JAVA(38 lines)
Code
Loading syntax highlighter...

TEXT(15 lines)
Code
Loading syntax highlighter...

JAVA(27 lines)
Code
Loading syntax highlighter...

JAVA(31 lines)
Code
Loading syntax highlighter...

3. Bucket Sort: For Uniform Distributions

Bucket Sort works by distributing elements into buckets, sorting each bucket, and concatenating.

JAVA(36 lines)
Code
Loading syntax highlighter...

TEXT(9 lines)
Code
Loading syntax highlighter...

JAVA(29 lines)
Code
Loading syntax highlighter...

4. When to Use Which?

JAVA(28 lines)
Code
Loading syntax highlighter...

⚠️ Common Mistakes

Mistake 1: Forgetting About Negative Numbers

JAVA(21 lines)
Code
Loading syntax highlighter...

Mistake 2: Using Radix Sort When Range Is Huge

JAVA(6 lines)
Code
Loading syntax highlighter...

Mistake 3: Unstable Counting Sort Breaking Radix Sort

JAVA(17 lines)
Code
Loading syntax highlighter...

🐛 Debug This

The following Radix Sort produces wrong results. Find the bug:

JAVA(36 lines)
Code
Loading syntax highlighter...

TEXT(5 lines)
Code
Loading syntax highlighter...

JAVA(31 lines)
Code
Loading syntax highlighter...

💻 Exercises

Exercise 1: Sort Strings by Length ⭐

Use Counting Sort to sort strings by their length:

JAVA(4 lines)
Code
Loading syntax highlighter...

JAVA(28 lines)
Code
Loading syntax highlighter...

Exercise 2: MSD Radix Sort ⭐⭐

Implement Most Significant Digit (MSD) Radix Sort:

JAVA(4 lines)
Code
Loading syntax highlighter...

JAVA(39 lines)
Code
Loading syntax highlighter...

Exercise 3: Sort IP Addresses ⭐⭐

Sort IP addresses (as strings) efficiently:

JAVA(5 lines)
Code
Loading syntax highlighter...

JAVA(55 lines)
Code
Loading syntax highlighter...
Show all 55 lines

Exercise 4: Hybrid Sort ⭐⭐⭐

Implement a hybrid sort that chooses the best algorithm:

JAVA(3 lines)
Code
Loading syntax highlighter...

JAVA(56 lines)
Code
Loading syntax highlighter...
Show all 56 lines

Exercise 5: External Radix Sort ⭐⭐⭐⭐

Implement Radix Sort for data too large to fit in memory:

JAVA(4 lines)
Code
Loading syntax highlighter...

JAVA(68 lines)
Code
Loading syntax highlighter...
Show all 68 lines

🎤 Interview Questions

Question #1: When would you use Counting Sort over QuickSort?

1. Keys are integers in a known, small range [0, k]
2. k ≤ n log n: If range k exceeds n log n, QuickSort is faster
   • Example: n=1M, k=20M → Counting Sort
   • Example: n=1M, k=1B → QuickSort
3. Stability is needed: Counting Sort is naturally stable
4. Memory is available: Needs O(k) extra space

• Sorting grades (0-100) for 10,000 students → Counting Sort (k=100, n=10000)
• Sorting salaries ($0-$10M) for 1000 employees → QuickSort (k=10M >> n log n)

Question #2: Why does Radix Sort use LSD (Least Significant Digit) order?

• After sorting by ones digit: numbers ending in 0 come first, etc.
• After sorting by tens digit: stability ensures numbers with same tens digit remain sorted by ones

• MSD must recursively sort each bucket separately
• Can't rely on a global stable sort because higher digits are more significant
• More complex but can short-circuit for variable-length strings

[170, 45, 75, 90]
After ones:  [170, 90, 45, 75]  (0s, then 5s)
After tens:  [45, 70, 75, 90]   (4,7,7,9 - stable keeps 70<75)
After hundreds: [45, 75, 90, 170]

Question #3: How would you sort 1 billion 32-bit integers with only 1GB RAM?

• Split into ~8 chunks of 125M integers each
• Sort each chunk in memory with QuickSort
• K-way merge the sorted chunks

• 4 passes (one per byte)
• Each pass: distribute to 256 buckets (files)
• Concatenate buckets

• If range is <1B distinct values, use streaming counting
• First pass: count occurrences (bitmap or count array)
• Second pass: output values in order

• Predictable I/O pattern
• Only 4 passes over the data
• ~10 minutes for 1B integers on SSD

Question #4: Explain why Bucket Sort degrades to O(n²) with non-uniform distribution.

• If uniform: each bucket has O(n/k) elements
• Sorting each bucket: O((n/k)²) with insertion sort
• Total: k × O((n/k)²) = O(n²/k)
• With k=n: O(n)

• All elements in one bucket: O(n²)
• Example: [0.001, 0.002, 0.003, ...] all go to bucket 0

1. Use comparison sort for buckets (O(n/k log n/k))
2. Adaptive bucket sizing based on samples
3. Hybrid: switch to QuickSort if bucket too large

Question #5: How would you sort strings alphabetically using Radix Sort?

1. Sort by first character (256-way counting sort)
2. Recursively sort each bucket by remaining characters
3. Stop when single character or empty

Optimization: Switch to insertion sort for small buckets

1. Pad all strings to max length
2. Sort from rightmost character to leftmost
3. Use stable counting sort for each position

Problem: Wastes space/time with variable lengths

• Partition by first character
• Recursively sort substrings
• Combines QuickSort efficiency with string structure

📋 Quick Reference

Algorithm Selection

Complexity Summary

Code Templates

JAVA(13 lines)
Code
Loading syntax highlighter...

📝 Summary & Key Takeaways

Core Principles

1. Linear sorts bypass Ω(n log n) by not using comparisons
2. Counting Sort: O(n+k) when k (range) is small
3. Radix Sort: O(d(n+k)) for fixed-width integers
4. Bucket Sort: O(n) for uniformly distributed data
5. Trade-off: speed vs assumptions - linear sorts have requirements

What You Can Do Now

• Implement all three linear sorting algorithms
• Choose the right algorithm based on data characteristics
• Handle edge cases (negatives, large ranges)
• Combine linear sorts with comparison sorts for hybrid approaches
• Analyze when O(n) sorts beat O(n log n) in practice

📅 Review Schedule