Counting Sort & Radix Sort — Negative Number Pitfalls

import java.util.Arrays;
import java.util.Random;

public class WhyLinearSortingMatters {

    // Comparison-based sort — time grows as O(n log n)
    static void comparisonSort(int[] data) {
        Arrays.sort(data); // Java's dual-pivot QuickSort under the hood
    }

    // Non-comparison sort — time grows as O(n + k) where k is the value range
    static void countingSort(int[] data, int maxValue) {\n        int[] frequency = new int[maxValue + 1]; // bucket for every possible value\n\n        // Pass 1: count how many times each value appears\n        for (int value : data) {\n            frequency[value]++;\n        }

        // Pass 2: write values back in order using the frequency counts
        int writeIndex = 0;
        for (int value = 0; value <= maxValue; value++) {
            while (frequency[value] > 0) {
                data[writeIndex++] = value;
                frequency[value]--;
            }
        }
    }

    public static void main(String[] args) {
        Random rng = new Random(42);
        int dataSize = 1_000_000;
        int maxScore = 100; // exam scores: always 0-100

        int[] scoresForComparison = new int[dataSize];
        int[] scoresForCounting  = new int[dataSize];

        for (int i = 0; i < dataSize; i++) {
            int score = rng.nextInt(maxScore + 1);
            scoresForComparison[i] = score;
            scoresForCounting[i]   = score;
        }

        long start = System.nanoTime();
        comparisonSort(scoresForComparison);
        long comparisonMs = (System.nanoTime() - start) / 1_000_000;

        start = System.nanoTime();
        countingSort(scoresForCounting, maxScore);
        long countingMs = (System.nanoTime() - start) / 1_000_000;

        System.out.println("Sorting " + dataSize + " exam scores (0-100):");
        System.out.println("  Comparison-based (Arrays.sort): " + comparisonMs + " ms");
        System.out.println("  Counting Sort:                  " + countingMs  + " ms");
        System.out.println("  Results match: " + Arrays.equals(scoresForComparison, scoresForCounting));
    }
}

import java.util.Arrays;

public class StableCountingSort {

    /**
     * Stable Counting Sort for an array of Student records sorted by grade (0-100).
     * Stability means two students with the same grade keep their original order.
     */
    static class Student {
        String name;
        int    grade;

        Student(String name, int grade) {\n            this.name  = name;\n            this.grade = grade;\n        }

        @Override
        public String toString() {
            return name + "(" + grade + ")";
        }
    }

    static Student[] stableCountingSort(Student[] students, int maxGrade) {\n        int n = students.length;\n        int[] frequency = new int[maxGrade + 1];\n\n        // Pass 1: count how many students have each grade\n        for (Student student : students) {\n            frequency[student.grade]++;\n        }

        // Pass 2: prefix sum — frequency[g] now holds the starting output
        //         index for all students whose grade is exactly g
        for (int grade = 1; grade <= maxGrade; grade++) {
            frequency[grade] += frequency[grade - 1];
        }

        // Pass 3: place each student into the output array.
        //         Iterate RIGHT-TO-LEFT to preserve stability
        //         (last student seen at a grade goes to the rightmost slot for that grade).
        Student[] sorted = new Student[n];
        for (int i = n - 1; i >= 0; i--) {
            int grade = students[i].grade;
            // decrement first because prefix sum points one past the last slot
            sorted[--frequency[grade]] = students[i];
        }

        return sorted;
    }

    public static void main(String[] args) {
        Student[] classroom = {
            new Student("Alice",   85),
            new Student("Bob",     92),
            new Student("Carmen",  85), // same grade as Alice — should stay after Alice
            new Student("David",   78),
            new Student("Eva",     92), // same grade as Bob — should stay after Bob
            new Student("Frank",   65)
        };

        System.out.println("Before: " + Arrays.toString(classroom));

        Student[] sorted = stableCountingSort(classroom, 100);

        System.out.println("After:  " + Arrays.toString(sorted));
        System.out.println();
        System.out.println("Stability check:");
        System.out.println("  Alice(85) appears before Carmen(85)? " +
            (indexOfStudent(sorted, "Alice") < indexOfStudent(sorted, "Carmen")));
        System.out.println("  Bob(92)   appears before Eva(92)?   " +
            (indexOfStudent(sorted, "Bob")   < indexOfStudent(sorted, "Eva")));
    }

    static int indexOfStudent(Student[] arr, String name) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i].name.equals(name)) return i;
        }
        return -1;
    }
}

import java.util.Arrays;

public class RadixSortPhoneNumbers {

    /**
     * Extracts the digit at a specific position from a number.
     * position=0 → units digit, position=1 → tens digit, etc.
     */
    static int getDigit(int number, int position) {
        return (number / (int) Math.pow(10, position)) % 10;
    }

    /**
     * One pass of stable Counting Sort over a single digit position.
     * This is called once per digit, and it MUST be stable.
     */
    static int[] countingSortByDigit(int[] numbers, int digitPosition) {\n        int n         = numbers.length;\n        int BASE      = 10;           // decimal digits: 0-9\n        int[] count   = new int[BASE];\n        int[] output  = new int[n];\n\n        // Count occurrences of each digit at this position\n        for (int number : numbers) {\n            int digit = getDigit(number, digitPosition);\n            count[digit]++;\n        }

        // Prefix sum: convert counts to starting output indices
        for (int d = 1; d < BASE; d++) {
            count[d] += count[d - 1];
        }

        // Place elements into output — RIGHT TO LEFT for stability
        for (int i = n - 1; i >= 0; i--) {
            int digit = getDigit(numbers[i], digitPosition);
            output[--count[digit]] = numbers[i];
        }

        return output;
    }

    /**
     * Full LSD (Least Significant Digit) Radix Sort.
     * Works correctly for any non-negative integers.
     */
    static int[] radixSort(int[] numbers) {
        if (numbers.length == 0) return numbers;

        // Find the maximum value to know how many digit passes we need
        int maxValue = numbers[0];
        for (int number : numbers) {
            if (number > maxValue) maxValue = number;
        }

        int[] current = Arrays.copyOf(numbers, numbers.length);

        // Sort from the least significant digit up to the most significant
        for (int digitPosition = 0; maxValue / (int) Math.pow(10, digitPosition) > 0; digitPosition++) {\n            System.out.println(\"Pass \" + (digitPosition + 1)\n                + \" (digit position \" + digitPosition + \"): \" + Arrays.toString(current));\n            current = countingSortByDigit(current, digitPosition);\n        }\n\n        return current;\n    }\n\n    public static void main(String[] args) {\n        // Simulating 7-digit subscriber IDs (like the last 7 digits of a phone number)\n        int[] subscriberIds = {\n            3706142,\n            1234567,\n            9999001,\n            3706140,  // nearly identical to first entry — tests fine-grained ordering\n            5550199,\n            1000000,\n            2468135\n        };\n\n        System.out.println(\"Unsorted: \" + Arrays.toString(subscriberIds));\n        System.out.println();\n        System.out.println(\"Radix Sort passes:\");\n\n        int[] sortedIds = radixSort(subscriberIds);\n\n        System.out.println();\n        System.out.println(\"Sorted:   \" + Arrays.toString(sortedIds));\n\n        // Verify correctness against a comparison sort\n        int[] expected = Arrays.copyOf(subscriberIds, subscriberIds.length);\n        Arrays.sort(expected);\n        System.out.println(\"Correct:  \" + Arrays.equals(sortedIds, expected));\n    }\n}",
        "output": "Unsorted: [3706142, 1234567, 9999001, 3706140, 5550199, 1000000, 2468135]\n\nRadix Sort passes:\n  Pass 1 (digit position 0): [3706142, 1234567, 9999001, 3706140, 5550199, 1000000, 2468135]\n  Pass 2 (digit position 1): [3706140, 3706142, 9999001, 1000000, 2468135, 1234567, 5550199]\n  Pass 3 (digit position 2): [9999001, 1000000, 3706140, 3706142, 5550199, 1234567, 2468135]\n  Pass 4 (digit position 3): [1000000, 1234567, 2468135, 3706140, 3706142, 5550199, 9999001]\n  Pass 5 (digit position 4): [1000000, 1234567, 2468135, 3706140, 3706142, 5550199, 9999001]\n  Pass 6 (digit position 5): [1000000, 1234567, 2468135, 3706140, 3706142, 5550199, 9999001]\n  Pass 7 (digit position 6): [1000000, 1234567, 2468135, 3706140, 3706142, 5550199, 9999001]\n\nSorted:   [1000000, 1234567, 2468135, 3706140, 3706142, 5550199, 9999001]\nCorrect:  true"
      }

public class SortDecisionExample {
    // Example: sorting 10 million 32-bit integers
    // k = 2^32, far too large for Counting Sort.
    // d = 32 bits -> base 256 gives 4 passes.
    // Radix Sort is ideal.
    
    // Example: sorting 1000 test scores (0-100)
    // n=1000, k=100. Counting Sort uses 101-slot array.
    // Radix Sort would require 3 decimal passes or 1 byte pass.
    // Counting Sort wins because k < n.
    
    // Example: sorting 1000 strings of varying length
    // No integer mapping -> use MergeSort.
}

import java.util.Arrays;

/**
 * Real-world example: sorting IPv4 addresses.
 * An IPv4 address is just a 32-bit unsigned integer.
 * We sort them as longs to avoid sign issues.
 * This pattern appears in network routing tables and log analysers.
 */
public class RadixSortIPAddresses {

    // Convert a dotted-decimal IP string to a long (avoids sign-bit issues)
    static long ipToLong(String ipAddress) {
        String[] octets = ipAddress.split("\.");
        long result = 0;
        for (String octet : octets) {
            result = result * 256 + Long.parseLong(octet);
        }
        return result;
    }

    // Convert a long back to dotted-decimal string
    static String longToIp(long value) {
        return ((value >> 24) & 0xFF) + "."
             + ((value >> 16) & 0xFF) + "."
             + ((value >>  8) & 0xFF) + "."
             +  (value        & 0xFF);
    }

    // Counting Sort by one byte (8-bit digit, base 256) — more efficient than base 10
    static long[] countingSortByByte(long[] addresses, int bytePosition) {\n        int n      = addresses.length;\n        int BASE   = 256; // one byte at a time: 0-255\n        int[] count  = new int[BASE];\n        long[] output = new long[n];\n\n        for (long address : addresses) {\n            int byteValue = (int)((address >> (bytePosition * 8)) & 0xFF);\n            count[byteValue]++;\n        }

        for (int b = 1; b < BASE; b++) {
            count[b] += count[b - 1];
        }

        for (int i = n - 1; i >= 0; i--) {
            int byteValue = (int)((addresses[i] >> (bytePosition * 8)) & 0xFF);
            output[--count[byteValue]] = addresses[i];
        }

        return output;
    }

    static long[] radixSortIPs(long[] addresses) {
        long[] current = Arrays.copyOf(addresses, addresses.length);
        // IPv4 has 4 bytes — sort by each byte from least to most significant
        for (int bytePos = 0; bytePos < 4; bytePos++) {
            current = countingSortByByte(current, bytePos);
        }
        return current;
    }

    public static void main(String[] args) {
        String[] ipStrings = {
            "192.168.10.255",
            "10.0.0.1",
            "172.16.254.1",
            "192.168.1.1",
            "10.0.0.2",
            "8.8.8.8",
            "192.168.10.1"
        };

        long[] ipLongs = new long[ipStrings.length];
        for (int i = 0; i < ipStrings.length; i++) {
            ipLongs[i] = ipToLong(ipStrings[i]);
        }

        long[] sortedIps = radixSortIPs(ipLongs);

        System.out.println("Sorted IP addresses:");
        for (long ip : sortedIps) {
            System.out.println("  " + longToIp(ip));
        }
    }
}

# Counting Sort (stable prefix-sum version) — Python
def counting_sort(arr, max_val):
    n = len(arr)
    count = [0] * (max_val + 1)
    output = [0] * n
    for x in arr:
        count[x] += 1
    for i in range(1, max_val + 1):
        count[i] += count[i-1]
    for i in range(n-1, -1, -1):
        output[count[arr[i]] - 1] = arr[i]
        count[arr[i]] -= 1
    return output

# Radix Sort (LSD, base 10) — Python
def radix_sort(arr):
    max_val = max(arr)
    exp = 1
    while max_val // exp > 0:
        count = [0] * 10
        output = [0] * len(arr)
        for x in arr:
            count[(x // exp) % 10] += 1
        for i in range(1, 10):
            count[i] += count[i-1]
        for i in range(len(arr)-1, -1, -1):
            digit = (arr[i] // exp) % 10
            output[count[digit] - 1] = arr[i]
            count[digit] -= 1
        arr = output
        exp *= 10
    return arr

// io.thecodeforge — dsa tutorial

public class RadixTimeAnalysis {
    public static void main(String[] args) {
        int n = 1_000_000;
        int digits = 10; // 32-bit integer in base 10
        int base = 10;
        double operations = (double) n * digits * (n + base) / n;
        System.out.println("Approx ops per element: " + operations);
        // vs comparison sort ~ n log2 n ≈ 20 ops per el
        System.out.println("Comparison sort O(n log n): ~" + (int)(Math.log(n)/Math.log(2)) + " ops/el");
        System.out.println("Radix wins for fixed-width ints.");
    }
}

// io.thecodeforge — dsa tutorial

// LSD Radix Sort Pseudocode (Base 10)
function radixSort(int[] arr):
    int max = findMax(arr)
    int digits = countDigits(max)
    for int exp = 1; max / exp > 0; exp *= 10:
        countingSortByDigit(arr, exp)

function countingSortByDigit(int[] arr, int exp):
    int[] output = new int[arr.length]
    int[] count = new int[10]  // 0-9 digits
    
    for int val : arr:
        count[(val / exp) % 10]++
    
    // prefix sum for stability
    for i = 1 to 9:
        count[i] += count[i - 1]
    
    for i = arr.length - 1 down to 0:
        int digit = (arr[i] / exp) % 10
        output[count[digit] - 1] = arr[i]
        count[digit]--
    
    copy output back to arr