[{"_1":2,"_3":-5,"_4":-5},"loaderData",{"_5":6},"actionData","errors","routes/blog-tag",{"_7":8,"_9":10},"tag",{"_31":86,"_73":87,"_35":88},"articles",{"_11":12,"_13":14,"_15":16,"_17":16,"_18":19,"_20":21,"_22":23,"_24":23,"_25":16,"_26":27},"content",[30],"pageable",{"_28":21,"_29":19},"totalElements",1,"totalPages","size",10,"number",0,"first",true,"last","numberOfElements","empty",false,"page_number","page_size",{"_31":32,"_33":34,"_35":36,"_37":38,"_11":39,"_40":-5,"_41":23,"_42":27,"_43":44,"_45":46,"_47":48,"_49":50,"_51":52,"_53":52,"_54":55,"_56":57,"_58":59,"_60":52,"_61":62,"_63":64,"_65":66,"_67":68,"_69":70,"_71":72},"id",32,"title","Linear Time Sorting","slug","algorithms-part-5-linear-time-sorting","excerpt","Escape the O(n log n) lower bound using Counting Sort, Radix Sort, and Bucket Sort when data has bounded, integer keys.","# Algorithms Compendium Part 5: Linear Time Sorting\n\nThe 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.\n\nThese 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.\n\n## 📋 At a Glance\n\n| Algorithm | Time | Space | Stable | When to Use |\n|-----------|------|-------|--------|-------------|\n| Counting Sort | O(n + k) | O(k) | Yes | Small range integers |\n| Radix Sort | O(d × (n + k)) | O(n + k) | Yes | Fixed-width integers/strings |\n| Bucket Sort | O(n + k) | O(n + k) | Yes | Uniformly distributed data |\n\nWhere k = range of values, d = number of digits\n\n---\n\n## 🎯 What You'll Learn\n\nAfter reading this article, you will be able to:\n\n- **Implement Counting Sort** for integers with known range\n- **Apply Radix Sort** to sort millions of integers faster than QuickSort\n- **Use Bucket Sort** for uniformly distributed floating-point numbers\n- **Know when O(n) sorts beat O(n log n)** in practice\n- **Combine these algorithms** with comparison sorts for hybrid approaches\n- **Avoid common pitfalls** like negative numbers and memory overhead\n\n---\n\n## 🔥 Production Story: 100 Million Log Entries\n\nA 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).\n\n```java\n// ❌ Initial approach: MergeSort\npublic void sortLogs(List logs) {\n logs.sort(Comparator.comparing(LogEntry::getTimestamp));\n}\n// Time: ~45 seconds for 100M entries\n```\n\n**Analysis revealed:**\n- Timestamps were bounded (one day = 86.4M milliseconds)\n- Timestamps were dense (many entries per millisecond)\n- MergeSort was doing ~1.7 billion comparisons\n\n**The optimization:**\n\n```java\n// ✅ Counting Sort for bounded timestamps\npublic void sortLogsFast(List logs) {\n // One day in milliseconds\n int range = 86_400_000;\n\n // Count entries per millisecond\n List> buckets = new ArrayList<>(range);\n for (int i = 0; i < range; i++) {\n buckets.add(new ArrayList<>());\n }\n\n // Distribute into buckets\n long dayStart = getDayStart(logs.get(0).getTimestamp());\n for (LogEntry log : logs) {\n int bucket = (int)(log.getTimestamp() - dayStart);\n buckets.get(bucket).add(log);\n }\n\n // Collect in order\n logs.clear();\n for (List bucket : buckets) {\n logs.addAll(bucket);\n }\n}\n// Time: ~8 seconds for 100M entries (5.6x faster!)\n```\n\n**Further optimization with Radix Sort:**\n\n```java\n// ✅ Radix Sort on timestamp bytes\npublic void sortLogsRadix(LogEntry[] logs) {\n // Sort by timestamp using 4 passes (32-bit relative timestamp)\n for (int shift = 0; shift < 32; shift += 8) {\n countingSortByByte(logs, shift);\n }\n}\n// Time: ~4 seconds for 100M entries\n```\n\n**The lesson:** When data has bounded, integer keys, linear sorts can be dramatically faster than comparison sorts.\n\n---\n\n## 🧠 Mental Model: Trading Assumptions for Speed\n\nLinear time sorts work by avoiding comparisons entirely. Instead, they use direct addressing or arithmetic:\n\n```text\n┌─────────────────────────────────────────────────────────────────┐\n│ WHY LINEAR SORTS BREAK THE Ω(n log n) BOUND │\n├─────────────────────────────────────────────────────────────────┤\n│ │\n│ Comparison sorts: n log n bound from decision tree │\n│ │\n│ Linear sorts: Don't use comparisons! │\n│ │\n│ ┌─────────────────────────────────────────────────────────┐ │\n│ │ TRADE-OFFS │ │\n│ ├─────────────────────────────────────────────────────────┤ │\n│ │ │ │\n│ │ Counting Sort: Assumes integer keys in range [0, k] │ │\n│ │ Uses O(k) extra space │ │\n│ │ │ │\n│ │ Radix Sort: Assumes fixed-width keys (d digits) │ │\n│ │ Uses O(n + k) space per pass │ │\n│ │ │ │\n│ │ Bucket Sort: Assumes uniform distribution │ │\n│ │ Degrades to O(n²) if skewed │ │\n│ │ │ │\n│ └─────────────────────────────────────────────────────────┘ │\n│ │\n│ Key insight: These assumptions let us bypass the decision │\n│ tree entirely by using direct array indexing. │\n│ │\n└─────────────────────────────────────────────────────────────────┘\n```\n\n**When to use linear sorts:**\n\n```text\nIs data bounded integers?\n├── Yes, small range (k < n log n) ──────→ Counting Sort\n├── Yes, but large range ────────────────→ Radix Sort\n└── No, but uniformly distributed? ──────→ Bucket Sort\n\nIf none apply → Use comparison sort (QuickSort/TimSort)\n```\n\n---\n\n## 🔬 Deep Dive\n\n### 1. Counting Sort: The Foundation\n\nCounting Sort works by counting occurrences of each value, then using those counts to place elements directly.\n\n```java\n// ✅ Counting Sort for non-negative integers\npublic class CountingSort {\n\n public static void sort(int[] arr, int maxValue) {\n int[] count = new int[maxValue + 1];\n\n // Count occurrences\n for (int num : arr) {\n count[num]++;\n }\n\n // Overwrite array with sorted values\n int index = 0;\n for (int value = 0; value <= maxValue; value++) {\n while (count[value] > 0) {\n arr[index++] = value;\n count[value]--;\n }\n }\n }\n}\n```\n\n**Stable Counting Sort (for objects or as Radix Sort subroutine):**\n\n```java\n// ✅ Stable Counting Sort - preserves relative order\npublic static void stableCountingSort(int[] arr, int maxValue) {\n int n = arr.length;\n int[] count = new int[maxValue + 1];\n int[] output = new int[n];\n\n // Step 1: Count occurrences\n for (int num : arr) {\n count[num]++;\n }\n\n // Step 2: Convert counts to positions\n // count[i] will contain the position of the last element with value i\n for (int i = 1; i <= maxValue; i++) {\n count[i] += count[i - 1];\n }\n\n // Step 3: Build output array (traverse backwards for stability)\n for (int i = n - 1; i >= 0; i--) {\n int value = arr[i];\n output[count[value] - 1] = value;\n count[value]--;\n }\n\n // Step 4: Copy back\n System.arraycopy(output, 0, arr, 0, n);\n}\n```\n\n**Why traverse backwards for stability?**\n\n```text\nInput: [3a, 1, 3b, 2] (3a appears before 3b)\n\nAfter counting: count = [0, 1, 1, 2] (0 zeros, 1 one, 1 two, 2 threes)\nAfter prefix sum: count = [0, 1, 2, 4] (positions: 0 at 0, 1 at 1, 2 at 2, 3s at 3-4)\n\nProcessing backwards (for stability):\n- i=3: value=2, place at position 1, output = [_, 2, _, _]\n- i=2: value=3b, place at position 3, output = [_, 2, _, 3b]\n- i=1: value=1, place at position 0, output = [1, 2, _, 3b]\n- i=0: value=3a, place at position 2, output = [1, 2, 3a, 3b] ✓ Stable!\n```\n\n**Handling negative numbers:**\n\n```java\n// ✅ Counting Sort with negative numbers\npublic static void sortWithNegatives(int[] arr) {\n int min = Arrays.stream(arr).min().orElse(0);\n int max = Arrays.stream(arr).max().orElse(0);\n int range = max - min + 1;\n\n int[] count = new int[range];\n\n // Shift values to be non-negative\n for (int num : arr) {\n count[num - min]++;\n }\n\n int index = 0;\n for (int i = 0; i < range; i++) {\n while (count[i] > 0) {\n arr[index++] = i + min; // Shift back\n count[i]--;\n }\n }\n}\n```\n\n### 2. Radix Sort: Sorting by Digits\n\nRadix Sort sorts numbers digit by digit, using a stable sort (usually Counting Sort) for each digit.\n\n**LSD (Least Significant Digit) Radix Sort:**\n\n```java\n// ✅ LSD Radix Sort for non-negative integers\npublic class RadixSort {\n\n public static void sort(int[] arr) {\n int max = Arrays.stream(arr).max().orElse(0);\n\n // Sort by each digit (1s, 10s, 100s, ...)\n for (int exp = 1; max / exp > 0; exp *= 10) {\n countingSortByDigit(arr, exp);\n }\n }\n\n private static void countingSortByDigit(int[] arr, int exp) {\n int n = arr.length;\n int[] output = new int[n];\n int[] count = new int[10]; // Digits 0-9\n\n // Count occurrences of each digit\n for (int num : arr) {\n int digit = (num / exp) % 10;\n count[digit]++;\n }\n\n // Convert to positions\n for (int i = 1; i < 10; i++) {\n count[i] += count[i - 1];\n }\n\n // Build output (backwards for stability)\n for (int i = n - 1; i >= 0; i--) {\n int digit = (arr[i] / exp) % 10;\n output[count[digit] - 1] = arr[i];\n count[digit]--;\n }\n\n System.arraycopy(output, 0, arr, 0, n);\n }\n}\n```\n\n**Why LSD works:**\n\n```text\nInput: [170, 45, 75, 90, 2, 24, 802, 66]\n\nPass 1 (ones digit):\n [170, 90, 2, 802, 24, 45, 75, 66]\n 0 0 2 2 4 5 5 6\n\nPass 2 (tens digit):\n [2, 802, 24, 45, 66, 170, 75, 90]\n 0 0 2 4 6 7 7 9\n\nPass 3 (hundreds digit):\n [2, 24, 45, 66, 75, 90, 170, 802]\n 0 0 0 0 0 0 1 8\n\nSorted! Each pass maintains stability from previous passes.\n```\n\n**Handling negative numbers with Radix Sort:**\n\n```java\n// ✅ Radix Sort with negative numbers\npublic static void sortWithNegatives(int[] arr) {\n // Separate negatives and positives\n List negatives = new ArrayList<>();\n List positives = new ArrayList<>();\n\n for (int num : arr) {\n if (num < 0) negatives.add(-num); // Store absolute value\n else positives.add(num);\n }\n\n // Sort each group\n int[] negArr = negatives.stream().mapToInt(i -> i).toArray();\n int[] posArr = positives.stream().mapToInt(i -> i).toArray();\n\n RadixSort.sort(negArr);\n RadixSort.sort(posArr);\n\n // Combine: negatives reversed, then positives\n int idx = 0;\n for (int i = negArr.length - 1; i >= 0; i--) {\n arr[idx++] = -negArr[i];\n }\n for (int num : posArr) {\n arr[idx++] = num;\n }\n}\n```\n\n**Base-256 (byte) Radix Sort for maximum efficiency:**\n\n```java\n// ✅ Radix Sort using bytes (base 256)\npublic static void sortByBytes(int[] arr) {\n int[] temp = new int[arr.length];\n\n // 4 passes for 32-bit integers\n for (int shift = 0; shift < 32; shift += 8) {\n int[] count = new int[256];\n\n // Count\n for (int num : arr) {\n int byteVal = (num >> shift) & 0xFF;\n count[byteVal]++;\n }\n\n // Prefix sum\n for (int i = 1; i < 256; i++) {\n count[i] += count[i - 1];\n }\n\n // Build output\n for (int i = arr.length - 1; i >= 0; i--) {\n int byteVal = (arr[i] >> shift) & 0xFF;\n temp[--count[byteVal]] = arr[i];\n }\n\n // Swap arrays\n int[] swap = arr;\n arr = temp;\n temp = swap;\n }\n}\n```\n\n### 3. Bucket Sort: For Uniform Distributions\n\nBucket Sort works by distributing elements into buckets, sorting each bucket, and concatenating.\n\n```java\n// ✅ Bucket Sort for floating-point numbers in [0, 1)\npublic class BucketSort {\n\n public static void sort(double[] arr) {\n int n = arr.length;\n if (n <= 1) return;\n\n // Create n empty buckets\n @SuppressWarnings(\"unchecked\")\n List[] buckets = new ArrayList[n];\n for (int i = 0; i < n; i++) {\n buckets[i] = new ArrayList<>();\n }\n\n // Distribute elements into buckets\n for (double num : arr) {\n int bucketIndex = (int)(num * n);\n // Handle edge case: num exactly equals 1.0\n if (bucketIndex >= n) bucketIndex = n - 1;\n buckets[bucketIndex].add(num);\n }\n\n // Sort each bucket (insertion sort for small buckets)\n for (List bucket : buckets) {\n Collections.sort(bucket);\n }\n\n // Concatenate buckets\n int index = 0;\n for (List bucket : buckets) {\n for (double num : bucket) {\n arr[index++] = num;\n }\n }\n }\n}\n```\n\n**Why uniform distribution matters:**\n\n```text\nUniform distribution: Elements spread evenly across buckets\n├── Each bucket has O(1) elements on average\n├── Sorting each bucket is O(1)\n└── Total: O(n) buckets × O(1) = O(n)\n\nSkewed distribution: Most elements in few buckets\n├── Some buckets have O(n) elements\n├── Sorting those buckets is O(n²) with insertion sort\n└── Total: O(n²) worst case\n```\n\n**Bucket Sort for integers with known range:**\n\n```java\n// ✅ Bucket Sort for integers\npublic static void sortIntegers(int[] arr, int minVal, int maxVal) {\n int n = arr.length;\n int range = maxVal - minVal + 1;\n int bucketCount = Math.max(1, n / 10); // ~10 elements per bucket\n int bucketSize = (range + bucketCount - 1) / bucketCount;\n\n @SuppressWarnings(\"unchecked\")\n List[] buckets = new ArrayList[bucketCount];\n for (int i = 0; i < bucketCount; i++) {\n buckets[i] = new ArrayList<>();\n }\n\n // Distribute\n for (int num : arr) {\n int bucketIndex = (num - minVal) / bucketSize;\n if (bucketIndex >= bucketCount) bucketIndex = bucketCount - 1;\n buckets[bucketIndex].add(num);\n }\n\n // Sort and collect\n int index = 0;\n for (List bucket : buckets) {\n Collections.sort(bucket);\n for (int num : bucket) {\n arr[index++] = num;\n }\n }\n}\n```\n\n### 4. When to Use Which?\n\n**Decision framework:**\n\n```java\npublic static void optimalSort(int[] arr) {\n int n = arr.length;\n if (n < 64) {\n insertionSort(arr);\n return;\n }\n\n int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;\n for (int num : arr) {\n min = Math.min(min, num);\n max = Math.max(max, num);\n }\n long range = (long)max - min + 1;\n\n if (range <= n) {\n // Small range: Counting Sort O(n + k) ≈ O(n)\n countingSortWithRange(arr, min, max);\n } else if (range <= (long)n * Math.log(n) / Math.log(2)) {\n // Medium range: Still worth Counting Sort\n countingSortWithRange(arr, min, max);\n } else if (max <= 100_000_000) {\n // Large range but bounded: Radix Sort\n radixSortWithNegatives(arr);\n } else {\n // Unbounded or floating point: QuickSort\n Arrays.sort(arr);\n }\n}\n```\n\n---\n\n## ⚠️ Common Mistakes\n\n### Mistake 1: Forgetting About Negative Numbers\n\n```java\n// ❌ Crashes or wrong results with negative numbers\npublic static void countingSort(int[] arr) {\n int max = Arrays.stream(arr).max().orElse(0);\n int[] count = new int[max + 1]; // ArrayIndexOutOfBoundsException!\n\n for (int num : arr) {\n count[num]++; // Negative index!\n }\n}\n\n// ✅ Handle negative numbers\npublic static void countingSortSafe(int[] arr) {\n int min = Arrays.stream(arr).min().orElse(0);\n int max = Arrays.stream(arr).max().orElse(0);\n int range = max - min + 1;\n int[] count = new int[range];\n\n for (int num : arr) {\n count[num - min]++;\n }\n}\n```\n\n### Mistake 2: Using Radix Sort When Range Is Huge\n\n```java\n// ❌ Radix Sort on 64-bit timestamps - 8 passes, lots of work\nlong[] timestamps = getTimestamps();\nradixSort(timestamps); // 8 × O(n) = O(8n), but with high constants\n\n// ✅ Use comparison sort for unbounded/large ranges\nArrays.sort(timestamps); // O(n log n) but optimized\n```\n\n### Mistake 3: Unstable Counting Sort Breaking Radix Sort\n\n```java\n// ❌ Non-stable counting sort as Radix Sort subroutine\nprivate static void countingSortByDigit(int[] arr, int exp) {\n int[] count = new int[10];\n\n for (int num : arr) count[(num/exp) % 10]++;\n\n int index = 0;\n for (int digit = 0; digit < 10; digit++) {\n for (int num : arr) { // WRONG: destroys stability!\n if ((num/exp) % 10 == digit) {\n arr[index++] = num;\n }\n }\n }\n}\n\n// ✅ Stable version (use output array, traverse backwards)\n```\n\n---\n\n## 🐛 Debug This\n\nThe following Radix Sort produces wrong results. Find the bug:\n\n```java\npublic class BuggyRadixSort {\n\n public static void sort(int[] arr) {\n int max = Arrays.stream(arr).max().orElse(0);\n\n for (int exp = 1; exp <= max; exp *= 10) {\n countingSortByDigit(arr, exp);\n }\n }\n\n private static void countingSortByDigit(int[] arr, int exp) {\n int n = arr.length;\n int[] output = new int[n];\n int[] count = new int[10];\n\n for (int num : arr) {\n count[(num / exp) % 10]++;\n }\n\n for (int i = 1; i < 10; i++) {\n count[i] += count[i - 1];\n }\n\n for (int i = 0; i < n; i++) {\n int digit = (arr[i] / exp) % 10;\n output[count[digit] - 1] = arr[i];\n count[digit]--;\n }\n\n System.arraycopy(output, 0, arr, 0, n);\n }\n}\n\n// Test: sort([170, 45, 75, 90])\n// Expected: [45, 75, 90, 170]\n// Actual: [90, 45, 170, 75] (wrong!)\n```\n\n

Click to reveal the bug and solution

\n\n**The Bug:**\n\nTwo issues:\n\n1. **Loop condition**: `exp <= max` should be `max / exp > 0`\n - For max=170, `exp=1000` is included but shouldn't be\n\n2. **Not traversing backwards**: The output loop goes forwards, breaking stability\n\n**Trace with forward traversal:**\n```text\nInput: [170, 45, 75, 90]\n\nPass 1 (ones): digits are [0, 5, 5, 0]\nForward traversal places 170 first, then 45...\nResult: [170, 90, 45, 75] (45 and 75 swapped because both have digit 5)\n```\n\n**The Fix:**\n\n```java\npublic static void sort(int[] arr) {\n int max = Arrays.stream(arr).max().orElse(0);\n\n // ✅ Fix 1: Correct loop condition\n for (int exp = 1; max / exp > 0; exp *= 10) {\n countingSortByDigit(arr, exp);\n }\n}\n\nprivate static void countingSortByDigit(int[] arr, int exp) {\n int n = arr.length;\n int[] output = new int[n];\n int[] count = new int[10];\n\n for (int num : arr) {\n count[(num / exp) % 10]++;\n }\n\n for (int i = 1; i < 10; i++) {\n count[i] += count[i - 1];\n }\n\n // ✅ Fix 2: Traverse backwards for stability\n for (int i = n - 1; i >= 0; i--) {\n int digit = (arr[i] / exp) % 10;\n output[count[digit] - 1] = arr[i];\n count[digit]--;\n }\n\n System.arraycopy(output, 0, arr, 0, n);\n}\n```\n\n

\n\n---\n\n## 💻 Exercises\n\n### Exercise 1: Sort Strings by Length ⭐\n\nUse Counting Sort to sort strings by their length:\n\n```java\npublic static void sortByLength(String[] arr) {\n // Sort strings so shorter ones come first\n // Strings of same length should maintain relative order\n}\n```\n\n

Solution

\n\n```java\npublic static void sortByLength(String[] arr) {\n int maxLen = Arrays.stream(arr)\n .mapToInt(String::length)\n .max()\n .orElse(0);\n\n int[] count = new int[maxLen + 1];\n String[] output = new String[arr.length];\n\n // Count lengths\n for (String s : arr) {\n count[s.length()]++;\n }\n\n // Prefix sum\n for (int i = 1; i <= maxLen; i++) {\n count[i] += count[i - 1];\n }\n\n // Build output (backwards for stability)\n for (int i = arr.length - 1; i >= 0; i--) {\n int len = arr[i].length();\n output[count[len] - 1] = arr[i];\n count[len]--;\n }\n\n System.arraycopy(output, 0, arr, 0, arr.length);\n}\n```\n

\n\n---\n\n### Exercise 2: MSD Radix Sort ⭐⭐\n\nImplement Most Significant Digit (MSD) Radix Sort:\n\n```java\n// MSD sorts from left to right, recursively sorting each bucket\npublic static void msdRadixSort(int[] arr) {\n // Your code here\n}\n```\n\n

Solution

\n\n```java\npublic static void msdRadixSort(int[] arr) {\n int max = Arrays.stream(arr).max().orElse(0);\n int maxDigits = (int)Math.log10(max) + 1;\n\n msdRadixSort(arr, 0, arr.length - 1, maxDigits);\n}\n\nprivate static void msdRadixSort(int[] arr, int lo, int hi, int digit) {\n if (lo >= hi || digit <= 0) return;\n\n int[] count = new int[12]; // 0-9 + 2 for boundaries\n int exp = (int)Math.pow(10, digit - 1);\n\n // Count\n for (int i = lo; i <= hi; i++) {\n int d = (arr[i] / exp) % 10;\n count[d + 2]++;\n }\n\n // Prefix sum\n for (int i = 0; i < 11; i++) {\n count[i + 1] += count[i];\n }\n\n // Distribute\n int[] aux = new int[hi - lo + 1];\n for (int i = lo; i <= hi; i++) {\n int d = (arr[i] / exp) % 10;\n aux[count[d + 1]++] = arr[i];\n }\n\n // Copy back\n System.arraycopy(aux, 0, arr, lo, aux.length);\n\n // Recursively sort each bucket\n for (int d = 0; d < 10; d++) {\n msdRadixSort(arr, lo + count[d], lo + count[d + 1] - 1, digit - 1);\n }\n}\n```\n\nMSD is useful for variable-length strings (can stop early) but more complex than LSD.\n

\n\n---\n\n### Exercise 3: Sort IP Addresses ⭐⭐\n\nSort IP addresses (as strings) efficiently:\n\n```java\n// Example: [\"192.168.1.1\", \"10.0.0.1\", \"192.168.0.1\"]\n// Sorted: [\"10.0.0.1\", \"192.168.0.1\", \"192.168.1.1\"]\npublic static void sortIPAddresses(String[] ips) {\n // Your code here\n}\n```\n\n

Solution

\n\n```java\npublic static void sortIPAddresses(String[] ips) {\n // Convert to integers for radix sort\n int[] ipInts = new int[ips.length];\n Map intToIp = new HashMap<>();\n\n for (int i = 0; i < ips.length; i++) {\n int ipInt = ipToInt(ips[i]);\n ipInts[i] = ipInt;\n intToIp.put(ipInt, ips[i]);\n }\n\n // Radix sort the integers\n radixSort(ipInts);\n\n // Convert back\n for (int i = 0; i < ips.length; i++) {\n ips[i] = intToIp.get(ipInts[i]);\n }\n}\n\nprivate static int ipToInt(String ip) {\n String[] octets = ip.split(\"\\\\.\");\n return (Integer.parseInt(octets[0]) << 24) |\n (Integer.parseInt(octets[1]) << 16) |\n (Integer.parseInt(octets[2]) << 8) |\n Integer.parseInt(octets[3]);\n}\n\n// Alternative: Radix sort directly on octets\npublic static void sortIPAddressesDirect(String[] ips) {\n // 4 passes: by 4th octet, 3rd, 2nd, 1st\n for (int octet = 3; octet >= 0; octet--) {\n final int idx = octet;\n countingSortByOctet(ips, idx);\n }\n}\n\nprivate static void countingSortByOctet(String[] ips, int octetIndex) {\n int[] count = new int[257];\n String[] output = new String[ips.length];\n\n for (String ip : ips) {\n int octet = Integer.parseInt(ip.split(\"\\\\.\")[octetIndex]);\n count[octet + 1]++;\n }\n\n for (int i = 1; i < 257; i++) count[i] += count[i - 1];\n\n for (int i = ips.length - 1; i >= 0; i--) {\n int octet = Integer.parseInt(ips[i].split(\"\\\\.\")[octetIndex]);\n output[count[octet]++] = ips[i];\n }\n\n System.arraycopy(output, 0, ips, 0, ips.length);\n}\n```\n

\n\n---\n\n### Exercise 4: Hybrid Sort ⭐⭐⭐\n\nImplement a hybrid sort that chooses the best algorithm:\n\n```java\npublic static void hybridSort(int[] arr) {\n // Analyze data characteristics and choose optimal algorithm\n}\n```\n\n

Solution

\n\n```java\npublic static void hybridSort(int[] arr) {\n int n = arr.length;\n\n if (n < 64) {\n insertionSort(arr, 0, n - 1);\n return;\n }\n\n // Find min and max\n int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;\n for (int num : arr) {\n min = Math.min(min, num);\n max = Math.max(max, num);\n }\n\n long range = (long)max - min + 1;\n double logN = Math.log(n) / Math.log(2);\n\n // Decision logic\n if (range <= n) {\n // Very dense: Counting Sort\n System.out.println(\"Using Counting Sort (range=\" + range + \")\");\n countingSortWithRange(arr, min, max);\n } else if (range <= n * logN) {\n // Moderately dense: Counting Sort still wins\n System.out.println(\"Using Counting Sort (range=\" + range + \", n*logN=\" + (n*logN) + \")\");\n countingSortWithRange(arr, min, max);\n } else if (max - min >= 0 && max <= 1_000_000_000) {\n // Bounded positive integers: Radix Sort\n System.out.println(\"Using Radix Sort\");\n radixSortNonNegative(arr);\n } else {\n // Fall back to QuickSort\n System.out.println(\"Using QuickSort\");\n Arrays.sort(arr);\n }\n}\n\nprivate static void countingSortWithRange(int[] arr, int min, int max) {\n int range = max - min + 1;\n int[] count = new int[range];\n\n for (int num : arr) count[num - min]++;\n\n int idx = 0;\n for (int i = 0; i < range; i++) {\n while (count[i]-- > 0) arr[idx++] = i + min;\n }\n}\n\nprivate static void radixSortNonNegative(int[] arr) {\n int max = Arrays.stream(arr).max().orElse(0);\n for (int exp = 1; max / exp > 0; exp *= 10) {\n countingSortByDigit(arr, exp);\n }\n}\n```\n

\n\n---\n\n### Exercise 5: External Radix Sort ⭐⭐⭐⭐\n\nImplement Radix Sort for data too large to fit in memory:\n\n```java\n// Sort a file containing integers, one per line\npublic static void externalRadixSort(Path inputFile, Path outputFile) {\n // Use file-based buckets for each pass\n}\n```\n\n

Solution

\n\n```java\npublic static void externalRadixSort(Path inputFile, Path outputFile) throws IOException {\n int maxDigits = findMaxDigits(inputFile);\n\n Path currentInput = inputFile;\n Path currentOutput = Files.createTempFile(\"radix\", \".tmp\");\n\n for (int digit = 0; digit < maxDigits; digit++) {\n distributeByDigit(currentInput, currentOutput, digit);\n\n if (digit > 0) Files.delete(currentInput);\n currentInput = currentOutput;\n currentOutput = Files.createTempFile(\"radix\", \".tmp\");\n }\n\n Files.move(currentInput, outputFile, StandardCopyOption.REPLACE_EXISTING);\n}\n\nprivate static int findMaxDigits(Path file) throws IOException {\n int max = 0;\n try (BufferedReader reader = Files.newBufferedReader(file)) {\n String line;\n while ((line = reader.readLine()) != null) {\n max = Math.max(max, Math.abs(Integer.parseInt(line)));\n }\n }\n return (int)Math.log10(max) + 1;\n}\n\nprivate static void distributeByDigit(Path input, Path output, int digitPos) throws IOException {\n int exp = (int)Math.pow(10, digitPos);\n\n // Create 10 bucket files\n Path[] buckets = new Path[10];\n BufferedWriter[] writers = new BufferedWriter[10];\n for (int i = 0; i < 10; i++) {\n buckets[i] = Files.createTempFile(\"bucket\" + i, \".tmp\");\n writers[i] = Files.newBufferedWriter(buckets[i]);\n }\n\n // Distribute\n try (BufferedReader reader = Files.newBufferedReader(input)) {\n String line;\n while ((line = reader.readLine()) != null) {\n int num = Integer.parseInt(line);\n int digit = Math.abs((num / exp) % 10);\n writers[digit].write(line);\n writers[digit].newLine();\n }\n }\n\n // Close writers\n for (BufferedWriter writer : writers) writer.close();\n\n // Concatenate buckets\n try (BufferedWriter outputWriter = Files.newBufferedWriter(output)) {\n for (int i = 0; i < 10; i++) {\n Files.lines(buckets[i]).forEach(line -> {\n try {\n outputWriter.write(line);\n outputWriter.newLine();\n } catch (IOException e) {\n throw new RuntimeException(e);\n }\n });\n Files.delete(buckets[i]);\n }\n }\n}\n```\n

\n\n---\n\n## 🎤 Interview Questions\n\n### Question #1: When would you use Counting Sort over QuickSort?\n\n**What interviewers want to hear**: Understanding of trade-offs and practical constraints.\n\n**Strong answer**:\nUse Counting Sort when:\n\n1. **Keys are integers** in a known, small range [0, k]\n\n2. **k ≤ n log n**: If range k exceeds n log n, QuickSort is faster\n - Example: n=1M, k=20M → Counting Sort\n - Example: n=1M, k=1B → QuickSort\n\n3. **Stability is needed**: Counting Sort is naturally stable\n\n4. **Memory is available**: Needs O(k) extra space\n\n**Real example:**\n- Sorting grades (0-100) for 10,000 students → Counting Sort (k=100, n=10000)\n- Sorting salaries ($0-$10M) for 1000 employees → QuickSort (k=10M >> n log n)\n\n---\n\n### Question #2: Why does Radix Sort use LSD (Least Significant Digit) order?\n\n**What interviewers want to hear**: Understanding of stability requirements.\n\n**Strong answer**:\nLSD works because each pass uses a **stable** sort, preserving relative order from previous passes.\n\n**Why it works:**\n- After sorting by ones digit: numbers ending in 0 come first, etc.\n- After sorting by tens digit: stability ensures numbers with same tens digit remain sorted by ones\n\n**Why MSD is different:**\n- MSD must recursively sort each bucket separately\n- Can't rely on a global stable sort because higher digits are more significant\n- More complex but can short-circuit for variable-length strings\n\n**Example with LSD:**\n```\n[170, 45, 75, 90]\nAfter ones: [170, 90, 45, 75] (0s, then 5s)\nAfter tens: [45, 70, 75, 90] (4,7,7,9 - stable keeps 70<75)\nAfter hundreds: [45, 75, 90, 170]\n```\n\n---\n\n### Question #3: How would you sort 1 billion 32-bit integers with only 1GB RAM?\n\n**What interviewers want to hear**: External sorting knowledge and practical problem-solving.\n\n**Strong answer**:\n1 billion integers = 4GB, exceeds 1GB RAM. Strategy:\n\n**Approach 1: External Merge Sort**\n- Split into ~8 chunks of 125M integers each\n- Sort each chunk in memory with QuickSort\n- K-way merge the sorted chunks\n\n**Approach 2: External Radix Sort**\n- 4 passes (one per byte)\n- Each pass: distribute to 256 buckets (files)\n- Concatenate buckets\n\n**Approach 3: Counting Sort variant (if range is small)**\n- If range is <1B distinct values, use streaming counting\n- First pass: count occurrences (bitmap or count array)\n- Second pass: output values in order\n\n**Best choice**: External Radix Sort\n- Predictable I/O pattern\n- Only 4 passes over the data\n- ~10 minutes for 1B integers on SSD\n\n---\n\n### Question #4: Explain why Bucket Sort degrades to O(n²) with non-uniform distribution.\n\n**What interviewers want to hear**: Understanding of algorithm assumptions.\n\n**Strong answer**:\nBucket Sort distributes n elements into k buckets, then sorts each bucket.\n\n**Analysis:**\n- If uniform: each bucket has O(n/k) elements\n- Sorting each bucket: O((n/k)²) with insertion sort\n- Total: k × O((n/k)²) = O(n²/k)\n- With k=n: O(n)\n\n**Non-uniform case:**\n- All elements in one bucket: O(n²)\n- Example: [0.001, 0.002, 0.003, ...] all go to bucket 0\n\n**Mitigations:**\n1. Use comparison sort for buckets (O(n/k log n/k))\n2. Adaptive bucket sizing based on samples\n3. Hybrid: switch to QuickSort if bucket too large\n\n---\n\n### Question #5: How would you sort strings alphabetically using Radix Sort?\n\n**What interviewers want to hear**: Extension of Radix Sort concepts to strings.\n\n**Strong answer**:\nTwo approaches:\n\n**MSD Radix Sort (most common for strings):**\n```\n1. Sort by first character (256-way counting sort)\n2. Recursively sort each bucket by remaining characters\n3. Stop when single character or empty\n\nOptimization: Switch to insertion sort for small buckets\n```\n\n**LSD with padding:**\n```\n1. Pad all strings to max length\n2. Sort from rightmost character to leftmost\n3. Use stable counting sort for each position\n\nProblem: Wastes space/time with variable lengths\n```\n\n**Comparison:**\n\n| Aspect | MSD | LSD |\n|--------|-----|-----|\n| Variable length | Natural | Needs padding |\n| Early termination | Yes | No |\n| Implementation | Complex (recursive) | Simple |\n| Cache behavior | Poor | Good |\n\n**Real implementation: 3-way String QuickSort**\n- Partition by first character\n- Recursively sort substrings\n- Combines QuickSort efficiency with string structure\n\n---\n\n## 📋 Quick Reference\n\n### Algorithm Selection\n\n| Condition | Best Algorithm |\n|-----------|----------------|\n| k ≤ n | Counting Sort |\n| k ≤ n log n | Counting Sort |\n| k > n log n, bounded integers | Radix Sort |\n| Uniform distribution floats | Bucket Sort |\n| General/unbounded | QuickSort/TimSort |\n\n### Complexity Summary\n\n| Algorithm | Time | Space | Stable | Requirements |\n|-----------|------|-------|--------|--------------|\n| Counting | O(n+k) | O(k) | Yes | Keys in [0,k] |\n| Radix (LSD) | O(d(n+k)) | O(n+k) | Yes | d-digit keys |\n| Radix (MSD) | O(n×len) | O(n+k) | Yes | Variable-length |\n| Bucket | O(n+k) | O(n+k) | Yes | Uniform dist |\n\n### Code Templates\n\n```java\n// Counting Sort core pattern\nint[] count = new int[range];\nfor (int num : arr) count[num - min]++;\nfor (int i = 1; i < range; i++) count[i] += count[i-1];\nfor (int i = n-1; i >= 0; i--) output[--count[arr[i] - min]] = arr[i];\n\n// Radix Sort core pattern\nfor (int exp = 1; max/exp > 0; exp *= 10)\n countingSortByDigit(arr, exp);\n\n// Bucket Sort core pattern\nfor (double num : arr) buckets[(int)(num * n)].add(num);\nfor (List bucket : buckets) Collections.sort(bucket);\n```\n\n---\n\n## 📝 Summary & Key Takeaways\n\n### Core Principles\n\n1. **Linear sorts bypass Ω(n log n)** by not using comparisons\n2. **Counting Sort: O(n+k)** when k (range) is small\n3. **Radix Sort: O(d(n+k))** for fixed-width integers\n4. **Bucket Sort: O(n)** for uniformly distributed data\n5. **Trade-off: speed vs assumptions** - linear sorts have requirements\n\n### What You Can Do Now\n\n- Implement all three linear sorting algorithms\n- Choose the right algorithm based on data characteristics\n- Handle edge cases (negatives, large ranges)\n- Combine linear sorts with comparison sorts for hybrid approaches\n- Analyze when O(n) sorts beat O(n log n) in practice\n\n---\n\n## 📅 Review Schedule\n\n| Day | Task | Time |\n|-----|------|------|\n| Day 1 | Review when to use each algorithm | 5 min |\n| Day 3 | Implement Counting Sort from memory | 10 min |\n| Day 7 | Implement Radix Sort from memory | 15 min |\n| Day 14 | Redo Debug This exercise | 10 min |\n| Day 30 | Solve the hybrid sort exercise | 20 min |\n\n---\n\n*Next in series: [Part 6: Sorting in Practice - Stability, External Sorting & Java's Arrays.sort()]*\n","featuredImage","isPublished","isFeatured","subscriptionType","BASIC","publishedAt","2026-06-10T07:19:25.066286Z","createdAt","2026-06-10T07:19:25.067021Z","updatedAt","2026-06-16T21:26:56.086200Z","readingTimeMinutes",22,"estimatedReadingTime","authorId",3,"authorUsername","tomasz_main","categoryName","Algorithms","readingTime","seriesId",2,"seriesOrder",5,"author",{"_31":55,"_99":57,"_100":101,"_102":103,"_104":-5,"_105":-5,"_106":-5,"_107":-5,"_108":-5},"category",{"_31":95,"_73":59,"_35":96,"_76":97,"_98":-5},"tags",[79,80,81,82],"series",{"_31":62,"_73":74,"_35":75,"_76":77,"_78":23},"name","Algorithms Compendium: From Theory to Production","algorithms-compendium","description","A comprehensive 23-part series covering all essential algorithms for Java developers. From foundational concepts like complexity analysis and recursion, through sorting (QuickSort, MergeSort, TimSort), searching (binary search, string matching), graph algorithms (DFS, BFS, Dijkstra, MST), dynamic programming, greedy algorithms, backtracking, to probabilistic data structures (Bloom filters, HyperLogLog) and interview patterns. Includes real production stories, mental models, exercises, and 100+ interview questions.","isActive",{"_31":92,"_73":93,"_35":94},{"_31":89,"_73":90,"_35":91},{"_31":86,"_73":87,"_35":88},{"_31":83,"_73":84,"_35":85},137,"Radix Sort","radix-sort",139,"Linear Time","linear-time",136,"Counting Sort","counting-sort",138,"Bucket Sort","bucket-sort",6,"algorithms","Category for Algorithms","colorHex","username","firstName","Tomasz","lastName","Jarosz","profilePicture","bio","website","githubUrl","linkedinUrl"]