Counting Sort and Radix Sort Explained — How to Sort in Linear Time

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) {
        int[] frequency = new int[maxValue + 1]; // bucket for every possible value

        // Pass 1: count how many times each value appears
        for (int value : data) {
            frequency[value]++;
        }

        // 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) {
            this.name  = name;
            this.grade = grade;
        }

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

    static Student[] stableCountingSort(Student[] students, int maxGrade) {
        int n = students.length;
        int[] frequency = new int[maxGrade + 1];

        // Pass 1: count how many students have each grade
        for (Student student : students) {
            frequency[student.grade]++;
        }

        // 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) {
        int n         = numbers.length;
        int BASE      = 10;           // decimal digits: 0-9
        int[] count   = new int[BASE];
        int[] output  = new int[n];

        // Count occurrences of each digit at this position
        for (int number : numbers) {
            int digit = getDigit(number, digitPosition);
            count[digit]++;
        }

        // 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++) {
            System.out.println("  Pass " + (digitPosition + 1)
                + " (digit position " + digitPosition + "): " + Arrays.toString(current));
            current = countingSortByDigit(current, digitPosition);
        }

        return current;
    }

    public static void main(String[] args) {
        // Simulating 7-digit subscriber IDs (like the last 7 digits of a phone number)
        int[] subscriberIds = {
            3706142,
            1234567,
            9999001,
            3706140,  // nearly identical to first entry — tests fine-grained ordering
            5550199,
            1000000,
            2468135
        };

        System.out.println("Unsorted: " + Arrays.toString(subscriberIds));
        System.out.println();
        System.out.println("Radix Sort passes:");

        int[] sortedIds = radixSort(subscriberIds);

        System.out.println();
        System.out.println("Sorted:   " + Arrays.toString(sortedIds));

        // Verify correctness against a comparison sort
        int[] expected = Arrays.copyOf(subscriberIds, subscriberIds.length);
        Arrays.sort(expected);
        System.out.println("Correct:  " + Arrays.equals(sortedIds, expected));
    }
}

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) {
        int n      = addresses.length;
        int BASE   = 256; // one byte at a time: 0-255
        int[] count  = new int[BASE];
        long[] output = new long[n];

        for (long address : addresses) {
            int byteValue = (int)((address >> (bytePosition * 8)) & 0xFF);
            count[byteValue]++;
        }

        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));
        }
    }
}