Counting & Bucket Sort

1. Introduction

What are Non-Comparison Sorts?

Non-Comparison Sorts are sorting algorithms that do not compare elements directly (like checking a < b). Instead, they exploit properties of the data—such as integer range bounds or uniform distributions—to group and sort elements in linear O(N) time.

Why study them?

These algorithms bypass the O(N log N) lower bound of comparison-based sorting. By knowing their trade-offs, you can pick specialized algorithms that are vastly faster for specific constraints.

Where are they Used?

Network Routing: Sorting IP packet routing indexes.

Computer Vision: Building color histograms and sorting pixel ranges.

Database Bucketing: Pre-sorting integer attributes for range queries.

---

2. Mental Models

Counting Sort: Labeled Mail Slots

Imagine sorting a stack of 100 letters that only have integer ratings from 0 to 5.

You lay out 6 mail slots labeled 0 through 5.

You scan the letters one by one, dropping each into its corresponding labeled slot.

Finally, you collect the letters from slot 0, then slot 1, up to slot 5. The letters are now sorted!

Bucket Sort: Sorting Mail by Zip Code

Imagine you need to sort letters for an entire state. You place several bins (buckets) representing ranges of zip codes (e.g., 90000-90999, 91000-91999).

You toss each letter into its matching range bucket.

You sort each bucket individually (e.g., using Insertion Sort).

You concatenate the sorted contents of all buckets from first to last.

---

3. Core Concepts & Implementations

Counting Sort

To ensure stability when sorting objects associated with integer keys, Counting Sort uses a prefix-sum array. This sum indicates the exact last index where each key belongs in the sorted array, allowing us to map elements from right-to-left.

---

4. Visual Trace: Counting Sort

Let's stably sort [1, 4, 1, 2, 7, 5, 2] using Counting Sort.

1. Calculate Frequencies: count = [0, 2, 2, 0, 1, 1, 0, 1] (indices 0 to 7)

2. Prefix Sum (Positions): count = [0, 2, 4, 4, 5, 6, 6, 7]

3. Placing Stably (Right-to-Left): - Element 2 at index 6: count[2] = 4. Output index 4 - 1 = 3. count[2] decrements to 3. - Element 5 at index 5: count[5] = 6. Output index 6 - 1 = 5. count[5] decrements to 5. - Element 7 at index 4: count[7] = 7. Output index 7 - 1 = 6. count[7] decrements to 6. - Element 2 at index 3: count[2] = 3. Output index 3 - 1 = 2. count[2] decrements to 2. - Element 1 at index 2: count[1] = 2. Output index 2 - 1 = 1. count[1] decrements to 1. - Element 4 at index 1: count[4] = 5. Output index 5 - 1 = 4. count[4] decrements to 4. - Element 1 at index 0: count[1] = 1. Output index 1 - 1 = 0. count[1] decrements to 0.

Sorted Output: [1, 1, 2, 2, 4, 5, 7]

---

5. Real-World Applications

Sorting Strings / IP Addresses (Radix Sort): Radix sort sorts elements digit-by-digit (or character-by-character) starting from the least significant digit. It relies on a stable counting sort as a subroutine, allowing strings of length L to be sorted in O(N × L) time.

Topological Sorting Pre-allocation: Compilers bucketing task dependencies where the range of dependencies is bounded by standard code package imports.

---

6. Interview Perspective

How Interviewers Ask This Topic

Interviewers verify whether you know the constraints of non-comparison sorts:

"Given an array of ages representing a country's population, sort it." -> Age is bounded (e.g. [0..120]), making Counting Sort run in O(N) time, which is much faster than standard O(N log N) sorting for millions of people.

"Sort an array of decimals uniformly distributed between 0 and 1." -> Bucket Sort is ideal.

Common Mistakes

> 2. Implementing Unstable Counting Sort: Simply writing a frequency map and iterating 1..K printing elements ignores object properties, producing an unstable sort. Always write the full prefix-sum and output array mapping.

---

7. Summary

Counting Sort: Highly efficient for small ranges. Time complexity is O(N + K) where K is the key range.

Bucket Sort: Divides interval into equal-sized buckets, sorts buckets, and concatenates. Optimal for uniformly distributed data.

Radix Sort: Sorts digit-by-digit to handle larger integer ranges stably.

---

8. Quiz

Question 1: Under what condition does Counting Sort run in linear O(N) time?

Answer: When the range of elements K is less than or equal to the size of the array N (i.e., K = O(N)). If K \gg N, the complexity O(N + K) degrades, becoming dominated by K.

Question 2: Why is the prefix-sum array and right-to-left iteration necessary in Counting Sort?

Answer: They guarantee stability. Iterating the original array from right-to-left and decrementing prefix sum coordinates ensures that identical keys are placed into the output array in the exact same relative order they entered.

Question 3: What is the average and worst-case time complexity of Bucket Sort?

Answer:

Average case: O(N) when elements are uniformly distributed across buckets.

Worst case: O(N²) when all elements are distributed into a single bucket, forcing the algorithm to fallback to insertion sort on the entire array.

Question 4: True or False: Non-comparison sorts violate the O(N log N) mathematical sorting lower bound.

Answer: False. The O(N log N) lower bound only applies to comparison-based sorting. Non-comparison sorts use assumptions about the keys (like indexing buckets directly), which doesn't rely on binary decision tree comparison limits.

Question 5: How does Radix Sort sort integers of range [0..10^6] stably without allocating a size-10^6 array?

Answer: It sorts digit-by-digit (e.g., base 10 or base 256). For base 10, it makes \approx 6 passes of Counting Sort, each pass allocating a tiny size-10 count array. This achieves sorting in O(6 × N) \approx O(N) time with minimal memory overhead.