Counting Sort and Radix Sort

# CHAPTER 18

Counting Sort and Radix Sort #

1. Introduction #

2. Learning Objectives #

• Explain the Non-Comparison algorithmic paradigm.

• Trace the frequency array mechanism of Counting Sort.

• Trace the digit-by-digit bucket mechanism of Radix Sort.

• Analyze the severe $O(K)$ Space Complexity tradeoffs.

• Identify when to use Radix Sort vs Quick Sort.

3. Counting Sort: The Execution Logic #

The Mechanics: Array: [4, 2, 2, 8, 3, 3, 1]

1. 1. Find Max: The highest number is 8.

1. 2. Create Frequency Array: Create a blank array with indices exactly 0 through 8.

1. 3. Tally Frequencies: Loop through the original data. Add +1 to the index matching the number.

1. 4. Rebuild: Loop through the Counts array from left to right, rebuilding the sorted array directly from the frequencies!

4. The Catastrophic Flaw of Counting Sort #

*Rule: Counting Sort is only viable when the absolute Maximum Value (K) in the dataset is small and heavily clustered.*

5. Radix Sort: The Savior #

The Mechanics: Array: [170, 45, 75, 90, 802, 24, 2, 66]

1. 1. Pass 1 (1s Place): Sort numbers strictly by their last digit.

1. 2. Pass 2 (10s Place): Sort numbers strictly by their middle digit. (Notice 802 and 2 act like 002).

1. 3. Pass 3 (100s Place): Sort numbers strictly by their first digit.

6. Implementation in Code #

// Java Example: Radix Sort
import java.util.*;

public class Radix {
    
    // The Execution Controller
    public static void radixSort(int[] arr) {
        int max = Arrays.stream(arr).max().getAsInt();
        
        // Execute Counting Sort digit-by-digit. (exp is 1, 10, 100...)
        for (int exp = 1; max / exp > 0; exp *= 10) {
            countingSortDigit(arr, exp);
        }
    }

    // The Inner Engine (A slightly modified Counting Sort)
    public static void countingSortDigit(int[] arr, int exp) {
        int n = arr.length;
        int[] output = new int[n];
        int[] count = new int[10]; // Radix Magic: We ONLY ever need 10 buckets!

        // Count frequencies based on the current isolated digit
        for (int i = 0; i < n; i++) {
            count[(arr[i] / exp) % 10]++;
        }

        // Calculate cumulative positions
        for (int i = 1; i < 10; i++) {
            count[i] += count[i - 1];
        }

        // Build the output array backwards to maintain Stability!
        for (int i = n - 1; i >= 0; i--) {
            int digit = (arr[i] / exp) % 10;
            output[count[digit] - 1] = arr[i];
            count[digit]--;
        }

        // Copy back to original
        System.arraycopy(output, 0, arr, 0, n);
    }
}

7. Complexity Analysis: True Linear Speed #

8. Stability Classification #

9. Real-World Applications #

• Big Data Analytics: If a supercomputer needs to sort 1 Billion integer IP Addresses or Zip Codes, Merge Sort ($O(N \log N)$) takes roughly 30 Billion operations. Radix Sort ($O(N \times K)$) takes roughly 5 Billion operations. At massive integer scales, Non-Comparison sorting saves phenomenal amounts of CPU time.

10. Common Mistakes #

• Applying to Strings or Floats: Junior developers hear "$O(N)$ speed" and try to Radix Sort an array of complex User Objects or negative floating-point decimals. The mathematical logic (number / exp % 10) shatters entirely on decimals and objects. Do not attempt this unless mapping strings explicitly to ASCII integer values.

11. Exercises #

1. 1. If your dataset contains negative numbers [-5, 2, -10, 8], why does the naive Counting Sort algorithm immediately throw an IndexOutOfBounds exception during Step 2?

1. 2. How many full array iterations (Passes) does Radix Sort require to completely sort an array whose maximum value is 45,291?

12. MCQs with Answers #

13. Interview Preparation #

• *Algorithmic Defense:* "If Radix Sort is mathematically $O(N)$ linear time, why does Python use Timsort ($O(N \log N)$) instead of Radix Sort as the default library engine?" *(Answer: Generalization! Standard libraries must be able to seamlessly sort Objects, Floats, and Strings using generalized comparison functions. Radix Sort is highly specialized and explicitly crashes on complex objects. Furthermore, if the integers are massive (e.g., 64-bit encryption keys), $K$ becomes huge, causing Radix's $O(N \times K)$ to actually run SLOWER than $O(N \log N)$!).*

14. Summary #

15. Next Chapter Recommendation #