[{"_1":2,"_3":-5,"_4":-5},"loaderData",{"_5":6},"actionData","errors","routes/blog-tag",{"_7":8,"_9":10},"tag",{"_31":96,"_73":97,"_35":98},"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",33,"title","Sorting in Practice","slug","algorithms-part-6-sorting-in-practice","excerpt","Bridge theory to practice: stability, Top-K selection, external sorting, parallel sorting, and writing correct Comparators for production systems.","# Algorithms Compendium Part 6: Sorting in Practice\n\nThe previous articles covered sorting algorithms in theory. This article bridges theory and practice: how to select the right algorithm, handle edge cases, sort datasets larger than memory, leverage parallel sorting, and write correct Comparators. These practical skills separate developers who \"know sorting\" from those who can apply it effectively.\n\n## 📋 At a Glance\n\n| Topic | Key Insight |\n|-------|-------------|\n| **Stability** | Preserves order of equal elements - critical for multi-key sorts |\n| **Top-K Selection** | Don't sort everything - O(n) with QuickSelect |\n| **External Sorting** | Merge sorted chunks when data exceeds RAM |\n| **Parallel Sorting** | Arrays.parallelSort() - 4-8x faster on multicore |\n| **Comparator Contracts** | Violating contracts causes crashes and wrong results |\n\n---\n\n## 🎯 What You'll Learn\n\nAfter reading this article, you will be able to:\n\n- **Explain stability** and know when it matters for business logic\n- **Solve Top-K problems** without sorting entire datasets\n- **Sort datasets larger than RAM** using external merge sort\n- **Leverage parallel sorting** effectively in Java\n- **Write correct Comparators** that won't crash production\n- **Select the right algorithm** for specific data characteristics\n\n---\n\n## 🔥 Production Story: The Mystery of Disappearing Sort Order\n\nAn e-commerce platform allowed users to sort products by multiple criteria. After sorting by price and then by rating, users expected products with the same rating to remain sorted by price. Instead, the order appeared random.\n\n```java\n// ❌ The problematic code\npublic List sortProducts(List products, String criterion) {\n if (\"price\".equals(criterion)) {\n products.sort(Comparator.comparing(Product::getPrice));\n } else if (\"rating\".equals(criterion)) {\n products.sort(Comparator.comparing(Product::getRating));\n }\n return products;\n}\n```\n\n**Investigation:**\n- Java's `List.sort()` uses TimSort (stable)\n- But `Arrays.sort()` for primitives used QuickSort (unstable)\n- A recent \"optimization\" converted the list to array before sorting:\n\n```java\n// ❌ The \"optimization\" that broke everything\npublic List sortProductsFast(List products, String criterion) {\n Product[] arr = products.toArray(new Product[0]);\n\n // This used Arrays.sort with primitive comparison indices\n // to avoid object comparisons - but lost stability!\n int[] indices = IntStream.range(0, arr.length).toArray();\n\n if (\"price\".equals(criterion)) {\n // Unstable sort on indices!\n Arrays.sort(indices, 0, indices.length); // Complex index manipulation\n }\n\n // Reconstruct...\n}\n```\n\n**The fix:**\n\n```java\n// ✅ Proper multi-key sorting\npublic List sortProducts(List products,\n List criteria) {\n // Build composite comparator\n Comparator comparator = criteria.stream()\n .map(this::toComparator)\n .reduce(Comparator::thenComparing)\n .orElse((a, b) -> 0);\n\n // TimSort is stable - multi-key sorting works correctly\n products.sort(comparator);\n return products;\n}\n\nprivate Comparator toComparator(SortCriterion criterion) {\n Comparator c = switch (criterion.field()) {\n case PRICE -> Comparator.comparing(Product::getPrice);\n case RATING -> Comparator.comparing(Product::getRating);\n case NAME -> Comparator.comparing(Product::getName);\n case DATE -> Comparator.comparing(Product::getCreatedAt);\n };\n return criterion.descending() ? c.reversed() : c;\n}\n```\n\n**The lesson:** Stability isn't academic - it's business logic. When users sort by rating and expect price order to be preserved, an unstable sort breaks user expectations.\n\n---\n\n## 🧠 Mental Model: The Sorting Decision Tree\n\n```text\nSORTING DECISION TREE\n━━━━━━━━━━━━━━━━━━━━━\n\n Start\n │\n ┌───────────┴───────────┐\n │ How much data? │\n └───────────┬───────────┘\n │\n ┌──────────────┼──────────────┐\n │ │ │\n < 50 items Fits in RAM > RAM size\n │ │ │\n Insertion Continue External\n Sort below Sort\n │ │ │\n └──────────────┴──────────────┘\n │\n ┌───────────┴───────────┐\n │ Need all sorted? │\n └───────────┬───────────┘\n │\n ┌───────┴───────┐\n │ │\n Need all Top-K only\n │ │\n Continue QuickSelect\n below O(n)\n │ │\n └───────┬───────┘\n │\n ┌───────────┴───────────┐\n │ Need stability? │\n └───────────┬───────────┘\n │\n ┌───────┴───────┐\n Yes, needed No need\n │ │\n MergeSort/ QuickSort/\n TimSort HeapSort\n │ │\n └───────┬───────┘\n │\n ┌───────────┴───────────┐\n │ Keys are integers │\n │ with small range? │\n └───────────┬───────────┘\n │\n ┌───────┴───────┐\n │ │\n Yes, bounded General\n │ │\n Counting/ Comparison\n Radix Sort Sort\n```\n\n---\n\n## 🔬 Deep Dive: Stability\n\n### What Is Stability?\n\nA sorting algorithm is **stable** if elements with equal keys maintain their relative order from the input.\n\n```java\npublic class StabilityDemo {\n record Student(String name, int grade) {}\n\n public static void main(String[] args) {\n List students = Arrays.asList(\n new Student(\"Alice\", 85),\n new Student(\"Bob\", 90),\n new Student(\"Charlie\", 85), // Same grade as Alice\n new Student(\"Diana\", 90) // Same grade as Bob\n );\n\n // Sort by grade\n // Stable sort: Alice before Charlie (both 85), Bob before Diana (both 90)\n // Unstable sort: Order among equal grades is undefined\n\n students.sort(Comparator.comparingInt(Student::grade));\n\n // With stable TimSort:\n // [Alice:85, Charlie:85, Bob:90, Diana:90]\n // Alice came before Charlie in input, remains before in output\n }\n}\n```\n\n### When Stability Matters\n\n**1. Multi-key sorting:**\n\n```java\n// Sort by department, then by hire date within department\nemployees.sort(Comparator.comparing(Employee::getHireDate));\nemployees.sort(Comparator.comparing(Employee::getDepartment));\n// With stable sort: employees in same department are still sorted by hire date\n```\n\n**2. Preserving user-defined order:**\n\n```java\n// User manually ordered items, then filters by category\n// Stable sort preserves manual order within each category\n```\n\n**3. Consistent results:**\n\n```java\n// Same input should produce same output\n// Unstable sorts can vary between runs (depending on implementation)\n```\n\n### Java Sorting Stability Reference\n\n| Method | Algorithm | Stable? |\n|--------|-----------|---------|\n| `Arrays.sort(Object[])` | TimSort | Yes |\n| `Arrays.sort(int[])` | Dual-Pivot QuickSort | No |\n| `Collections.sort()` | TimSort | Yes |\n| `List.sort()` | TimSort | Yes |\n| `Arrays.parallelSort(Object[])` | Parallel MergeSort | Yes |\n| `Arrays.parallelSort(int[])` | Parallel QuickSort variant | No |\n| `Stream.sorted()` | TimSort | Yes |\n\n### Making Unstable Sorts Stable\n\n```java\n/**\n * Decorator that makes any comparator stable by using\n * original index as tiebreaker.\n */\npublic class StableSort {\n public static void sort(T[] arr, Comparator comparator) {\n // Pair each element with its original index\n @SuppressWarnings(\"unchecked\")\n IndexedElement[] indexed = new IndexedElement[arr.length];\n for (int i = 0; i < arr.length; i++) {\n indexed[i] = new IndexedElement<>(arr[i], i);\n }\n\n // Sort with original index as tiebreaker\n Arrays.sort(indexed, (a, b) -> {\n int cmp = comparator.compare(a.element, b.element);\n return cmp != 0 ? cmp : Integer.compare(a.index, b.index);\n });\n\n // Copy back\n for (int i = 0; i < arr.length; i++) {\n arr[i] = indexed[i].element;\n }\n }\n\n private record IndexedElement(T element, int index) {}\n}\n```\n\n---\n\n## 🔬 Deep Dive: Top-K Selection\n\n### The Problem\n\n\"Find the K largest elements\" is one of the most common sorting-related problems. Sorting the entire array is wasteful when you only need K elements.\n\n```text\nInput: [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5], K = 3\nOutput: [9, 6, 5] (three largest)\n\nFull sort: O(n log n) = O(11 × 3.5) ≈ 38 operations\nSelection: O(n) = 11 operations\n```\n\n### Approach 1: Min-Heap (O(n log k))\n\nKeep a min-heap of size K. For each element, add it and remove the minimum if heap exceeds K.\n\n```java\npublic class TopKHeap {\n /**\n * Find K largest elements using a min-heap.\n * Time: O(n log k), Space: O(k)\n */\n public static > List topK(List elements, int k) {\n if (k <= 0) return Collections.emptyList();\n if (k >= elements.size()) {\n List result = new ArrayList<>(elements);\n result.sort(Comparator.reverseOrder());\n return result;\n }\n\n // Min-heap: smallest at top\n PriorityQueue minHeap = new PriorityQueue<>(k);\n\n for (T element : elements) {\n if (minHeap.size() < k) {\n minHeap.offer(element);\n } else if (element.compareTo(minHeap.peek()) > 0) {\n // Current element is larger than smallest in heap\n minHeap.poll();\n minHeap.offer(element);\n }\n }\n\n // Extract in descending order\n List result = new ArrayList<>(k);\n while (!minHeap.isEmpty()) {\n result.add(minHeap.poll());\n }\n Collections.reverse(result);\n return result;\n }\n\n public static void main(String[] args) {\n List numbers = Arrays.asList(3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5);\n System.out.println(topK(numbers, 3)); // [9, 6, 5]\n }\n}\n```\n\n### Approach 2: QuickSelect (O(n) average)\n\nPartition-based selection finds the K-th element without fully sorting.\n\n```java\npublic class QuickSelect {\n private static final Random random = new Random();\n\n /**\n * Find K largest elements using QuickSelect.\n * Time: O(n) average, O(n²) worst\n * Space: O(1) - modifies input array\n */\n public static int[] topK(int[] arr, int k) {\n if (k <= 0) return new int[0];\n if (k >= arr.length) {\n int[] result = arr.clone();\n Arrays.sort(result);\n return result;\n }\n\n // Partition so that arr[n-k:] contains K largest (not sorted)\n int targetIndex = arr.length - k;\n quickSelect(arr, 0, arr.length - 1, targetIndex);\n\n // Extract and sort the K largest\n int[] result = Arrays.copyOfRange(arr, targetIndex, arr.length);\n Arrays.sort(result);\n reverseArray(result);\n return result;\n }\n\n /**\n * Partition array so element at targetIndex is in correct position.\n */\n private static void quickSelect(int[] arr, int lo, int hi, int targetIndex) {\n while (lo < hi) {\n int pivotIndex = partition(arr, lo, hi);\n\n if (pivotIndex == targetIndex) {\n return;\n } else if (pivotIndex < targetIndex) {\n lo = pivotIndex + 1;\n } else {\n hi = pivotIndex - 1;\n }\n }\n }\n\n private static int partition(int[] arr, int lo, int hi) {\n // Random pivot to avoid O(n²) on sorted input\n int pivotIndex = lo + random.nextInt(hi - lo + 1);\n int pivot = arr[pivotIndex];\n swap(arr, pivotIndex, hi);\n\n int storeIndex = lo;\n for (int i = lo; i < hi; i++) {\n if (arr[i] < pivot) {\n swap(arr, i, storeIndex);\n storeIndex++;\n }\n }\n swap(arr, storeIndex, hi);\n return storeIndex;\n }\n\n private static void swap(int[] arr, int i, int j) {\n int tmp = arr[i];\n arr[i] = arr[j];\n arr[j] = tmp;\n }\n\n private static void reverseArray(int[] arr) {\n for (int i = 0, j = arr.length - 1; i < j; i++, j--) {\n swap(arr, i, j);\n }\n }\n}\n```\n\n### Approach 3: Partial Sort with Heap (O(n + k log n))\n\nBuild a max-heap in O(n), then extract K elements in O(k log n).\n\n```java\npublic class PartialHeapSort {\n /**\n * Find K largest using heapify + K extractions.\n * Time: O(n + k log n), Space: O(1) - in-place\n */\n public static int[] topK(int[] arr, int k) {\n if (k <= 0) return new int[0];\n if (k >= arr.length) {\n int[] result = arr.clone();\n Arrays.sort(result);\n reverseArray(result);\n return result;\n }\n\n // Build max-heap in O(n)\n int n = arr.length;\n for (int i = n / 2 - 1; i >= 0; i--) {\n heapify(arr, n, i);\n }\n\n // Extract K largest in O(k log n)\n int[] result = new int[k];\n for (int i = 0; i < k; i++) {\n result[i] = arr[0];\n arr[0] = arr[n - 1 - i];\n heapify(arr, n - 1 - i, 0);\n }\n\n return result;\n }\n\n private static void heapify(int[] arr, int n, int i) {\n int largest = i;\n int left = 2 * i + 1;\n int right = 2 * i + 2;\n\n if (left < n && arr[left] > arr[largest]) {\n largest = left;\n }\n if (right < n && arr[right] > arr[largest]) {\n largest = right;\n }\n\n if (largest != i) {\n int tmp = arr[i];\n arr[i] = arr[largest];\n arr[largest] = tmp;\n heapify(arr, n, largest);\n }\n }\n\n private static void reverseArray(int[] arr) {\n for (int i = 0, j = arr.length - 1; i < j; i++, j--) {\n int tmp = arr[i];\n arr[i] = arr[j];\n arr[j] = tmp;\n }\n }\n}\n```\n\n### Top-K Algorithm Selection\n\n| Algorithm | Time | Space | Best For |\n|-----------|------|-------|----------|\n| Min-Heap | O(n log k) | O(k) | Streaming data, memory-constrained |\n| QuickSelect | O(n) avg | O(1)* | Large arrays, k << n |\n| Partial HeapSort | O(n + k log n) | O(1)* | K close to n |\n| Full Sort | O(n log n) | O(n) | Need sorted output |\n\n*Modifies input array\n\n---\n\n## 🔬 Deep Dive: External Sorting\n\n### The Problem\n\nWhen data doesn't fit in memory, we need to sort in chunks and merge.\n\n```text\nScenario: Sort 100GB of records on a machine with 8GB RAM\n\nApproach:\n1. Read 8GB chunk → Sort in memory → Write to temp file\n2. Repeat for all chunks (creates ~13 sorted files)\n3. Merge sorted files together\n```\n\n### External Merge Sort Implementation\n\n```java\npublic class ExternalSort {\n private static final int CHUNK_SIZE = 100_000_000; // ~100MB assuming 1 byte/record\n\n /**\n * Sort a file that doesn't fit in memory.\n * @param inputPath Input file with one number per line\n * @param outputPath Sorted output file\n * @param availableMemoryMB RAM available for sorting\n */\n public static void sort(Path inputPath, Path outputPath, int availableMemoryMB)\n throws IOException {\n // Phase 1: Create sorted chunks\n List sortedChunks = createSortedChunks(inputPath, availableMemoryMB);\n\n // Phase 2: Merge sorted chunks\n mergeChunks(sortedChunks, outputPath);\n\n // Cleanup\n for (Path chunk : sortedChunks) {\n Files.deleteIfExists(chunk);\n }\n }\n\n /**\n * Phase 1: Read chunks, sort in memory, write to temp files.\n */\n private static List createSortedChunks(Path inputPath, int availableMemoryMB)\n throws IOException {\n List chunks = new ArrayList<>();\n\n // Estimate how many longs fit in available memory\n int chunkSize = (availableMemoryMB * 1024 * 1024) / 8; // 8 bytes per long\n\n try (BufferedReader reader = Files.newBufferedReader(inputPath)) {\n List buffer = new ArrayList<>(chunkSize);\n String line;\n\n while ((line = reader.readLine()) != null) {\n buffer.add(Long.parseLong(line.trim()));\n\n if (buffer.size() >= chunkSize) {\n chunks.add(sortAndWriteChunk(buffer));\n buffer.clear();\n }\n }\n\n // Handle remaining data\n if (!buffer.isEmpty()) {\n chunks.add(sortAndWriteChunk(buffer));\n }\n }\n\n return chunks;\n }\n\n private static Path sortAndWriteChunk(List data) throws IOException {\n // Sort in memory\n Collections.sort(data);\n\n // Write to temp file\n Path tempFile = Files.createTempFile(\"sort_chunk_\", \".tmp\");\n try (BufferedWriter writer = Files.newBufferedWriter(tempFile)) {\n for (Long value : data) {\n writer.write(value.toString());\n writer.newLine();\n }\n }\n\n return tempFile;\n }\n\n /**\n * Phase 2: K-way merge of sorted chunks.\n */\n private static void mergeChunks(List chunks, Path outputPath)\n throws IOException {\n // Priority queue for K-way merge\n PriorityQueue pq = new PriorityQueue<>(\n Comparator.comparingLong(ChunkReader::peek)\n );\n\n // Open all chunk readers\n List readers = new ArrayList<>();\n try {\n for (Path chunk : chunks) {\n BufferedReader reader = Files.newBufferedReader(chunk);\n readers.add(reader);\n ChunkReader chunkReader = new ChunkReader(reader);\n if (chunkReader.hasNext()) {\n pq.offer(chunkReader);\n }\n }\n\n // Merge\n try (BufferedWriter writer = Files.newBufferedWriter(outputPath)) {\n while (!pq.isEmpty()) {\n ChunkReader smallest = pq.poll();\n writer.write(Long.toString(smallest.next()));\n writer.newLine();\n\n if (smallest.hasNext()) {\n pq.offer(smallest);\n }\n }\n }\n } finally {\n for (BufferedReader reader : readers) {\n reader.close();\n }\n }\n }\n\n /**\n * Helper class to read from sorted chunk file.\n */\n private static class ChunkReader {\n private final BufferedReader reader;\n private Long current;\n\n ChunkReader(BufferedReader reader) throws IOException {\n this.reader = reader;\n advance();\n }\n\n boolean hasNext() {\n return current != null;\n }\n\n long peek() {\n return current;\n }\n\n long next() throws IOException {\n long value = current;\n advance();\n return value;\n }\n\n private void advance() throws IOException {\n String line = reader.readLine();\n current = (line != null) ? Long.parseLong(line.trim()) : null;\n }\n }\n}\n```\n\n### External Sort with Replacement Selection\n\nFor better chunk sizes, use **replacement selection** - it can produce chunks up to 2× memory size for nearly-sorted input.\n\n```java\npublic class ReplacementSelectionSort {\n /**\n * Create sorted run using replacement selection.\n * Can produce runs up to 2x heap size for nearly-sorted input.\n */\n public static Path createSortedRun(Iterator input, int heapSize,\n Path outputDir) throws IOException {\n PriorityQueue heap = new PriorityQueue<>(\n Comparator.comparingInt(HeapElement::generation)\n .thenComparingLong(HeapElement::value)\n );\n\n int currentGeneration = 0;\n\n // Fill initial heap\n while (heap.size() < heapSize && input.hasNext()) {\n heap.offer(new HeapElement(input.next(), currentGeneration));\n }\n\n Path outputFile = Files.createTempFile(outputDir, \"run_\", \".tmp\");\n\n try (BufferedWriter writer = Files.newBufferedWriter(outputFile)) {\n Long lastOutput = null;\n\n while (!heap.isEmpty()) {\n HeapElement smallest = heap.poll();\n\n // Start new run if we've wrapped around\n if (smallest.generation > currentGeneration) {\n // In production: would start new file\n currentGeneration = smallest.generation;\n }\n\n writer.write(Long.toString(smallest.value));\n writer.newLine();\n lastOutput = smallest.value;\n\n // Replace with next input\n if (input.hasNext()) {\n long nextValue = input.next();\n int gen = (nextValue >= lastOutput)\n ? currentGeneration\n : currentGeneration + 1;\n heap.offer(new HeapElement(nextValue, gen));\n }\n }\n }\n\n return outputFile;\n }\n\n private record HeapElement(long value, int generation) {}\n}\n```\n\n### External Sort Complexity\n\n| Phase | Time | I/O |\n|-------|------|-----|\n| Create Chunks | O(n log m) | Read n, Write n |\n| K-way Merge | O(n log k) | Read n, Write n |\n| **Total** | O(n log m) | 4n |\n\nWhere n = total records, m = chunk size, k = number of chunks\n\n---\n\n## 🔬 Deep Dive: Parallel Sorting in Java\n\n### Arrays.parallelSort()\n\nJava 8 introduced `Arrays.parallelSort()` - a parallel merge sort that uses the Fork/Join framework.\n\n```java\npublic class ParallelSortDemo {\n public static void main(String[] args) {\n int size = 100_000_000;\n int[] data = new int[size];\n Random random = new Random();\n\n // Initialize with random data\n for (int i = 0; i < size; i++) {\n data[i] = random.nextInt();\n }\n\n int[] copy = data.clone();\n\n // Sequential sort\n long start = System.nanoTime();\n Arrays.sort(data);\n long seqTime = System.nanoTime() - start;\n\n // Parallel sort\n start = System.nanoTime();\n Arrays.parallelSort(copy);\n long parTime = System.nanoTime() - start;\n\n System.out.printf(\"Sequential: %.2f seconds%n\", seqTime / 1e9);\n System.out.printf(\"Parallel: %.2f seconds%n\", parTime / 1e9);\n System.out.printf(\"Speedup: %.2fx%n\", (double) seqTime / parTime);\n\n // Typical output on 8-core machine:\n // Sequential: 12.34 seconds\n // Parallel: 2.45 seconds\n // Speedup: 5.04x\n }\n}\n```\n\n### How parallelSort() Works\n\n```text\nPARALLEL MERGE SORT STRUCTURE\n━━━━━━━━━━━━━━━━━━━━━━━━━━━━\n\n [Full Array]\n │\n ┌─────────────┴─────────────┐\n │ │\n [Left Half] [Right Half]\n │ │\n ┌─────┴─────┐ ┌─────┴─────┐\n │ │ │ │\n [Q1] [Q2] [Q3] [Q4]\n │ │ │ │\n ↓ ↓ ↓ ↓\n Thread 1 Thread 2 Thread 3 Thread 4\n (sort Q1) (sort Q2) (sort Q3) (sort Q4)\n │ │ │ │\n └─────┬─────┘ └─────┬─────┘\n │ │\n Merge L1+L2 Merge L3+L4\n │ │\n └─────────────┬─────────────┘\n │\n Final Merge\n```\n\n### When parallelSort() Helps\n\n```java\npublic class ParallelSortBenchmark {\n\n // Threshold where parallel starts to help\n // Java uses MIN_ARRAY_SORT_GRAN = 1 << 13 = 8192\n private static final int PARALLEL_THRESHOLD = 8192;\n\n public static void benchmark() {\n int[] sizes = {1000, 10_000, 100_000, 1_000_000, 10_000_000};\n\n for (int size : sizes) {\n int[] data = generateRandomArray(size);\n int[] copy = data.clone();\n\n long seqTime = measureSort(data, Arrays::sort);\n long parTime = measureSort(copy, Arrays::parallelSort);\n\n System.out.printf(\"Size: %,10d | Seq: %,8d us | Par: %,8d us | \" +\n \"Speedup: %.2fx%n\",\n size, seqTime / 1000, parTime / 1000,\n (double) seqTime / parTime);\n }\n }\n\n private static int[] generateRandomArray(int size) {\n Random r = new Random(42);\n int[] arr = new int[size];\n for (int i = 0; i < size; i++) {\n arr[i] = r.nextInt();\n }\n return arr;\n }\n\n private static long measureSort(int[] arr, java.util.function.Consumer sorter) {\n long start = System.nanoTime();\n sorter.accept(arr);\n return System.nanoTime() - start;\n }\n\n /*\n Typical results (8-core machine):\n\n Size: 1,000 | Seq: 45 us | Par: 89 us | Speedup: 0.51x\n Size: 10,000 | Seq: 523 us | Par: 287 us | Speedup: 1.82x\n Size: 100,000 | Seq: 6,234 us | Par: 1,456 us | Speedup: 4.28x\n Size: 1,000,000 | Seq: 78,456 us | Par: 15,234 us | Speedup: 5.15x\n Size: 10,000,000 | Seq: 923,456 us | Par: 172,345 us | Speedup: 5.36x\n\n Key insight: parallelSort() overhead makes it slower for small arrays!\n */\n}\n```\n\n### Custom Parallel Sorting with Fork/Join\n\n```java\npublic class CustomParallelSort {\n private static final int THRESHOLD = 10_000;\n\n public static void parallelQuickSort(int[] arr) {\n ForkJoinPool pool = ForkJoinPool.commonPool();\n pool.invoke(new QuickSortTask(arr, 0, arr.length - 1));\n }\n\n private static class QuickSortTask extends RecursiveAction {\n private final int[] arr;\n private final int lo, hi;\n\n QuickSortTask(int[] arr, int lo, int hi) {\n this.arr = arr;\n this.lo = lo;\n this.hi = hi;\n }\n\n @Override\n protected void compute() {\n if (hi - lo < THRESHOLD) {\n // Fall back to sequential sort for small chunks\n Arrays.sort(arr, lo, hi + 1);\n return;\n }\n\n int pivot = partition(arr, lo, hi);\n\n // Fork both subtasks\n QuickSortTask left = new QuickSortTask(arr, lo, pivot - 1);\n QuickSortTask right = new QuickSortTask(arr, pivot + 1, hi);\n\n left.fork();\n right.compute(); // Compute right in current thread\n left.join(); // Wait for left\n }\n\n private int partition(int[] arr, int lo, int hi) {\n int pivot = arr[hi];\n int i = lo - 1;\n\n for (int j = lo; j < hi; j++) {\n if (arr[j] <= pivot) {\n i++;\n swap(arr, i, j);\n }\n }\n swap(arr, i + 1, hi);\n return i + 1;\n }\n\n private void swap(int[] arr, int i, int j) {\n int tmp = arr[i];\n arr[i] = arr[j];\n arr[j] = tmp;\n }\n }\n}\n```\n\n---\n\n## 🔬 Deep Dive: Comparator Best Practices\n\n### The Comparator Contract\n\nA Comparator must satisfy three properties:\n\n1. **Antisymmetry**: `compare(a, b) > 0` implies `compare(b, a) < 0`\n2. **Transitivity**: `compare(a, b) > 0` and `compare(b, c) > 0` implies `compare(a, c) > 0`\n3. **Consistency**: `compare(a, b) == 0` implies `sign(compare(a, c)) == sign(compare(b, c))`\n\n### Common Comparator Mistakes\n\n**Mistake 1: Subtraction overflow**\n\n```java\n// ❌ DANGEROUS: Integer overflow!\nComparator BAD_COMPARATOR = (a, b) -> a - b;\n\n// With a = Integer.MAX_VALUE, b = -1:\n// a - b = Integer.MAX_VALUE - (-1) = Integer.MIN_VALUE (overflow!)\n// Returns negative, suggesting MAX_VALUE < -1!\n\n// ✅ CORRECT\nComparator GOOD_COMPARATOR = Integer::compare;\n// Or: Comparator.comparingInt(x -> x)\n```\n\n**Mistake 2: NaN handling in doubles**\n\n```java\n// ❌ NaN breaks transitivity\nComparator BAD_DOUBLE_COMP = (a, b) -> {\n if (a < b) return -1;\n if (a > b) return 1;\n return 0;\n};\n// Double.NaN is neither < nor > any value!\n\n// ✅ Use Double.compare which handles NaN\nComparator GOOD_DOUBLE_COMP = Double::compare;\n// NaN is considered greater than any other value\n```\n\n**Mistake 3: Inconsistent with equals**\n\n```java\nrecord Person(String name, int age) {}\n\n// ❌ Two persons can compare equal but not be equals()\nComparator AGE_ONLY = Comparator.comparingInt(Person::age);\n// Person(\"Alice\", 30) and Person(\"Bob\", 30) compare as equal\n// But they're not equals()\n\n// This causes issues with TreeSet/TreeMap which use comparator for equality\nTreeSet set = new TreeSet<>(AGE_ONLY);\nset.add(new Person(\"Alice\", 30));\nset.add(new Person(\"Bob\", 30)); // Not added! Considered duplicate\n\n// ✅ Use thenComparing for unique ordering\nComparator FULL_COMP = Comparator\n .comparingInt(Person::age)\n .thenComparing(Person::name);\n```\n\n**Mistake 4: Null handling**\n\n```java\n// ❌ NullPointerException waiting to happen\nComparator BAD = String::compareTo;\n\n// ✅ Handle nulls explicitly\nComparator NULLS_FIRST = Comparator.nullsFirst(String::compareTo);\nComparator NULLS_LAST = Comparator.nullsLast(String::compareTo);\n\n// ✅ For nested fields\nComparator BY_MANAGER = Comparator.comparing(\n Employee::getManager,\n Comparator.nullsLast(Comparator.comparing(Manager::getName))\n);\n```\n\n### Building Complex Comparators\n\n```java\npublic class ComparatorExamples {\n record Product(String name, BigDecimal price, int rating, LocalDate added) {}\n\n // ✅ Fluent comparator building\n public static Comparator createProductComparator(\n List sortFields) {\n\n Comparator comparator = null;\n\n for (SortField field : sortFields) {\n Comparator fieldComp = switch (field.name()) {\n case \"name\" -> Comparator.comparing(Product::name,\n String.CASE_INSENSITIVE_ORDER);\n case \"price\" -> Comparator.comparing(Product::price);\n case \"rating\" -> Comparator.comparingInt(Product::rating);\n case \"added\" -> Comparator.comparing(Product::added);\n default -> throw new IllegalArgumentException(\n \"Unknown field: \" + field.name());\n };\n\n if (field.descending()) {\n fieldComp = fieldComp.reversed();\n }\n\n comparator = (comparator == null)\n ? fieldComp\n : comparator.thenComparing(fieldComp);\n }\n\n return comparator != null ? comparator : (a, b) -> 0;\n }\n\n record SortField(String name, boolean descending) {}\n}\n```\n\n### Comparator Performance\n\n```java\npublic class ComparatorPerformance {\n record Data(String key, int value) {}\n\n public static void benchmark() {\n List data = generateData(1_000_000);\n\n // Method reference - fastest\n Comparator methodRef = Comparator.comparing(Data::key);\n\n // Lambda - nearly as fast\n Comparator lambda = Comparator.comparing(d -> d.key());\n\n // Anonymous class - slightly slower (but JIT optimizes)\n Comparator anon = new Comparator<>() {\n @Override\n public int compare(Data a, Data b) {\n return a.key().compareTo(b.key());\n }\n };\n\n // Multiple thenComparing - chaining has overhead\n Comparator chained = Comparator\n .comparing(Data::key)\n .thenComparingInt(Data::value);\n\n /*\n Typical results (sorting 1M elements):\n - Method reference: ~850ms\n - Lambda: ~860ms\n - Anonymous class: ~870ms\n - Chained (2 keys): ~920ms\n\n The overhead is minimal - choose for readability!\n */\n }\n\n private static List generateData(int size) {\n Random r = new Random();\n return IntStream.range(0, size)\n .mapToObj(i -> new Data(\n String.valueOf(r.nextInt(10000)),\n r.nextInt()\n ))\n .collect(Collectors.toList());\n }\n}\n```\n\n---\n\n## ⚠️ Common Mistakes\n\n### Mistake 1: Ignoring Stability Requirements\n\n```java\n// ❌ Using primitive sort when stability matters\nint[] indices = new int[items.length];\nfor (int i = 0; i < indices.length; i++) indices[i] = i;\n\n// Unstable! Order of equal elements undefined\nArrays.sort(indices, 0, indices.length);\n\n// ✅ Use object sort for stability\nInteger[] indicesObj = new Integer[items.length];\nfor (int i = 0; i < indicesObj.length; i++) indicesObj[i] = i;\nArrays.sort(indicesObj, comparator); // TimSort - stable\n```\n\n### Mistake 2: Sorting When Selection Suffices\n\n```java\n// ❌ Sorting entire array for top 10\nList scores = getMillionScores();\nscores.sort(Comparator.reverseOrder());\nreturn scores.subList(0, 10);\n// Time: O(n log n)\n\n// ✅ Use a min-heap\nPriorityQueue topK = new PriorityQueue<>(10);\nfor (Score s : getMillionScores()) {\n if (topK.size() < 10) {\n topK.offer(s);\n } else if (s.compareTo(topK.peek()) > 0) {\n topK.poll();\n topK.offer(s);\n }\n}\n// Time: O(n log k) where k = 10\n```\n\n### Mistake 3: External Sort Without Considering Memory\n\n```java\n// ❌ Loading everything into memory first\nList all = Files.lines(hugefile)\n .map(Record::parse)\n .collect(Collectors.toList()); // OutOfMemoryError!\nall.sort(comparator);\n\n// ✅ Use external sort\nExternalSort.sort(inputPath, outputPath,\n Runtime.getRuntime().maxMemory() / (1024 * 1024) / 2);\n```\n\n### Mistake 4: Wrong parallelSort() Usage\n\n```java\n// ❌ Parallel sort on small array (overhead > benefit)\nint[] small = new int[100];\nArrays.parallelSort(small); // Slower than sort()!\n\n// ❌ Parallel sort on already-sorted array\n// Both sorts are O(n log n), but overhead makes parallel worse\n\n// ✅ Use parallel only for large random arrays\nif (data.length > 10_000 && !isNearlySorted(data)) {\n Arrays.parallelSort(data);\n} else {\n Arrays.sort(data);\n}\n```\n\n---\n\n## 🐛 Debug This: The Broken Comparator\n\nThis code has multiple Comparator-related bugs. Find and fix them:\n\n```java\npublic class BrokenSort {\n record Transaction(\n String id,\n LocalDateTime timestamp,\n BigDecimal amount,\n String category\n ) {}\n\n public List sortTransactions(\n List transactions,\n String sortBy,\n boolean ascending) {\n\n Comparator comparator = switch (sortBy) {\n case \"timestamp\" -> (a, b) ->\n a.timestamp().compareTo(b.timestamp());\n case \"amount\" -> (a, b) ->\n a.amount().subtract(b.amount()).intValue(); // Bug 1\n case \"category\" -> (a, b) ->\n a.category().compareTo(b.category()); // Bug 2\n default -> (a, b) -> 0;\n };\n\n if (!ascending) {\n comparator = (a, b) -> comparator.compare(b, a); // Bug 3\n }\n\n transactions.sort(comparator);\n return transactions;\n }\n\n // Bug 4: Test fails intermittently\n public void testSort() {\n List txns = Arrays.asList(\n new Transaction(\"1\", LocalDateTime.now(),\n new BigDecimal(\"100.50\"), \"Food\"),\n new Transaction(\"2\", LocalDateTime.now().minusHours(1),\n new BigDecimal(\"50.25\"), null),\n new Transaction(\"3\", LocalDateTime.now().minusHours(2),\n new BigDecimal(\"200.75\"), \"Transport\")\n );\n\n sortTransactions(txns, \"category\", true);\n // Expected: null first or last?\n }\n}\n```\n\n

💡 Hint

\n\nLook for:\n1. BigDecimal comparison issues\n2. Null handling\n3. Variable capture in lambda\n4. Consistency requirements\n\n

\n\n

✅ Solution

\n\n```java\npublic class FixedSort {\n record Transaction(\n String id,\n LocalDateTime timestamp,\n BigDecimal amount,\n String category\n ) {}\n\n public List sortTransactions(\n List transactions,\n String sortBy,\n boolean ascending) {\n\n Comparator comparator = switch (sortBy) {\n // ✅ Fix 1: Use proper LocalDateTime comparison\n case \"timestamp\" -> Comparator.comparing(\n Transaction::timestamp,\n Comparator.nullsLast(Comparator.naturalOrder())\n );\n\n // ✅ Fix 2: Use BigDecimal.compareTo, not subtract().intValue()\n // subtract().intValue() loses precision and can overflow\n case \"amount\" -> Comparator.comparing(\n Transaction::amount,\n Comparator.nullsLast(Comparator.naturalOrder())\n );\n\n // ✅ Fix 3: Handle null categories\n case \"category\" -> Comparator.comparing(\n Transaction::category,\n Comparator.nullsFirst(String.CASE_INSENSITIVE_ORDER)\n );\n\n default -> (a, b) -> 0;\n };\n\n // ✅ Fix 4: Use reversed() instead of lambda capture issue\n if (!ascending) {\n comparator = comparator.reversed();\n }\n\n // ✅ Fix 5: Don't modify input list\n List result = new ArrayList<>(transactions);\n result.sort(comparator);\n return result;\n }\n}\n```\n\n**Bugs explained:**\n\n1. **BigDecimal subtraction**: `amount.subtract().intValue()` loses decimal precision and can overflow for large values. Always use `compareTo()`.\n\n2. **Null categories**: `a.category().compareTo(b.category())` throws NullPointerException when category is null.\n\n3. **Lambda capture**: The original `(a, b) -> comparator.compare(b, a)` captures the `comparator` variable. While it works here, it's cleaner and more efficient to use `comparator.reversed()`.\n\n4. **Mutating input**: The original code modified the input list, which can cause issues for callers.\n\n

\n\n---\n\n## 💻 Exercises\n\n### Exercise 1: Stable Selection Sort ⭐\n\nImplement a selection sort that maintains stability for equal elements.\n\n```java\npublic class StableSelectionSort {\n /**\n * Sort array using stable selection sort.\n * Standard selection sort is unstable - fix it.\n */\n public static > void sort(T[] arr) {\n // Your implementation\n }\n}\n```\n\n

💡 Hint

\n\nInstead of swapping, shift elements to insert the minimum in place.\n\n

\n\n---\n\n### Exercise 2: Streaming Top-K ⭐⭐\n\nImplement a class that maintains the top K elements from a stream.\n\n```java\npublic class StreamingTopK> {\n /**\n * Create a streaming top-K tracker.\n * @param k Number of top elements to track\n */\n public StreamingTopK(int k) {\n // Your implementation\n }\n\n /**\n * Add an element to the stream.\n * Time: O(log k)\n */\n public void add(T element) {\n // Your implementation\n }\n\n /**\n * Get the current top K elements (sorted descending).\n * Time: O(k log k)\n */\n public List getTopK() {\n // Your implementation\n }\n}\n```\n\n---\n\n### Exercise 3: External Sort with Custom Comparator ⭐⭐⭐\n\nExtend the external sort to support:\n1. Custom objects (not just primitives)\n2. Any Comparator\n3. Configurable merge fan-in (how many files to merge at once)\n\n```java\npublic class GenericExternalSort {\n /**\n * Sort a large file of serializable objects.\n * @param inputFile File containing serialized objects\n * @param outputFile Destination for sorted objects\n * @param comparator Ordering for objects\n * @param chunkSize Number of objects per memory chunk\n * @param mergeFanIn Number of files to merge simultaneously\n */\n public void sort(Path inputFile, Path outputFile,\n Comparator comparator,\n int chunkSize, int mergeFanIn) throws IOException {\n // Your implementation\n }\n}\n```\n\n---\n\n### Exercise 4: Adaptive parallelSort Wrapper ⭐⭐⭐\n\nCreate a wrapper that automatically decides between sequential and parallel sort based on array characteristics.\n\n```java\npublic class AdaptiveSort {\n /**\n * Sort using the best strategy for the given data.\n * Consider: size, sortedness, data distribution\n */\n public static void sort(int[] arr) {\n // Your implementation - detect characteristics and choose strategy\n }\n\n /**\n * Estimate sortedness (0.0 = random, 1.0 = sorted)\n */\n private static double estimateSortedness(int[] arr) {\n // Your implementation\n }\n}\n```\n\n

💡 Hint

\n\nSample random pairs and count inversions. If few inversions, data is nearly sorted and sequential TimSort/InsertionSort is better.\n\n

\n\n---\n\n### Exercise 5: Multi-Level External Sort ⭐⭐⭐⭐\n\nImplement a multi-level external sort that handles datasets so large they require multiple merge passes.\n\n```java\npublic class MultiLevelExternalSort {\n /**\n * Sort dataset requiring multiple merge passes.\n *\n * When K chunks > available file handles, merge in multiple levels:\n * Level 1: Merge groups of M chunks into intermediate files\n * Level 2: Merge intermediate files\n * ... until one file remains\n *\n * @param chunks Initial sorted chunks\n * @param maxOpenFiles Maximum simultaneous open files\n * @param outputPath Final sorted output\n */\n public void sort(List chunks, int maxOpenFiles, Path outputPath)\n throws IOException {\n // Your implementation\n }\n}\n```\n\n---\n\n## 🎤 Interview Questions\n\n### Question 1: Why is stability important?\n\n**Answer:**\nStability matters when:\n\n1. **Multi-key sorting**: Sort by secondary key first, then primary. Stable sort preserves secondary ordering within equal primary keys.\n\n2. **Preserving user order**: User manually ordered items, then applies filter/sort. Stable sort maintains manual order within groups.\n\n3. **Deterministic results**: Same input always produces same output. Unstable sorts may vary between runs.\n\n4. **Database consistency**: When sorting query results, stability ensures consistent pagination.\n\n**Example**:\n```java\n// Sort employees by department (secondary), then by salary (primary)\nemployees.sort(Comparator.comparing(Employee::getDepartment));\nemployees.sort(Comparator.comparing(Employee::getSalary)); // stable!\n// Result: Sorted by salary, with department order preserved within same salary\n```\n\n**Follow-up**: Java's TimSort is stable. Arrays.sort(primitives) uses Dual-Pivot QuickSort which is unstable - why the difference?\n\nAnswer: Primitives have no identity beyond value, so stability is meaningless. Objects may be distinct even with equal comparison keys.\n\n---\n\n### Question 2: How would you sort a 1TB file on a machine with 16GB RAM?\n\n**Answer:**\n\nUse external merge sort with these steps:\n\n1. **Chunk phase**: Read 8GB chunks (leave room for OS/overhead), sort with Arrays.parallelSort(), write to temp files. Creates ~128 sorted chunks.\n\n2. **Merge phase**: Open all chunks simultaneously (if file handles allow), use k-way merge with min-heap. Time: O(n log k) where k = 128.\n\n3. **Multi-level merge**: If k exceeds file handle limit (~1000 on Linux), merge in levels - groups of 500, then merge intermediate files.\n\n**Optimizations**:\n- Replacement selection: Can produce chunks up to 2x memory for partially sorted data\n- Buffer tuning: Large read/write buffers reduce I/O operations\n- SSD consideration: Random access penalty is lower, might use different strategy\n- Compression: Compress chunks to reduce I/O\n\n**Complexity**: O(n log n) with 4n I/O (2 passes: read+write for chunk, read+write for merge)\n\n---\n\n### Question 3: When would you NOT use parallelSort()?\n\n**Answer:**\n\n1. **Small arrays** (< 10,000 elements): Fork/Join overhead exceeds benefit\n2. **Nearly sorted data**: TimSort's O(n) on sorted data beats parallel's O(n log n)\n3. **Single-core systems**: No parallelism to exploit\n4. **Memory pressure**: Parallel sort uses additional memory for merging\n5. **Latency-sensitive code**: Thread scheduling adds variance\n6. **Within parallel streams**: Already using multiple threads\n\n**Benchmark rule**: Always measure. The crossover point depends on data size, CPU count, and memory.\n\n---\n\n### Question 4: Design a sorting system for a real-time leaderboard\n\n**Answer:**\n\nRequirements analysis:\n- Frequent updates (scores change)\n- Need top K quickly\n- May have millions of users\n\n**Approach 1: Balanced BST (TreeSet)**\n```java\nTreeSet leaderboard = new TreeSet<>(\n Comparator.comparingLong(Player::score).reversed()\n .thenComparing(Player::id)\n);\n```\n- Insert/update/delete: O(log n)\n- Top K: O(k) via iterator\n- Issue: Updates require remove + add\n\n**Approach 2: Skip List with Score Indexing**\n```java\n// Redis ZADD approach\n// Score -> Set of player IDs\nNavigableMap> scoreIndex = new ConcurrentSkipListMap<>();\n```\n- Updates: O(log n)\n- Top K: O(k) iteration\n- Better for concurrent updates\n\n**Approach 3: Bucket + Periodic Sort**\n- Divide score range into buckets\n- Maintain sorted list within each bucket\n- Top K: Iterate from highest bucket\n- Background thread re-balances\n\n**Follow-up**: How would you handle ties (same score)?\n\nUse secondary sort key (timestamp of achieving score, player ID) for deterministic ordering.\n\n---\n\n### Question 5: Explain the Comparator contract and what happens if you violate it\n\n**Answer:**\n\nThe Comparator contract requires:\n\n1. **Antisymmetry**: `sgn(compare(a,b)) == -sgn(compare(b,a))`\n2. **Transitivity**: `compare(a,b) > 0 && compare(b,c) > 0` implies `compare(a,c) > 0`\n3. **Consistency**: `compare(a,b) == 0` implies `sgn(compare(a,c)) == sgn(compare(b,c))`\n\n**Violations and consequences:**\n\n```java\n// ❌ Violates antisymmetry - subtraction overflow\nComparator broken = (a, b) -> a - b;\n// MAX_VALUE - (-1) overflows to MIN_VALUE (negative)\n// Says MAX_VALUE < -1!\n\n// Consequence: Infinite loops in sort, wrong results\n```\n\n```java\n// ❌ Violates transitivity - inconsistent with floating point\nComparator broken = (a, b) -> {\n if (Math.abs(a - b) < 0.01) return 0; // \"Close enough\"\n return Double.compare(a, b);\n};\n// 1.0 ≈ 1.005 ≈ 1.01, but 1.0 ≠ 1.01!\n\n// Consequence: Sort order depends on comparison sequence\n```\n\n```java\n// ❌ Violates consistency with equals\nComparator broken = String.CASE_INSENSITIVE_ORDER;\n// \"ABC\".equals(\"abc\") is false\n// But comparator says they're equal\n\n// Consequence: TreeSet/TreeMap treat them as duplicates\nTreeSet set = new TreeSet<>(broken);\nset.add(\"ABC\");\nset.add(\"abc\"); // Not added!\n```\n\n**TimSort specifically**: Violation can cause ArrayIndexOutOfBoundsException due to merge assumptions about ordering.\n\n---\n\n## 📋 Quick Reference\n\n### Algorithm Selection Matrix\n\n| Scenario | Algorithm | Rationale |\n|----------|-----------|-----------|\n| General purpose | TimSort (List.sort) | Adaptive, stable, O(n) on sorted |\n| Primitives | Dual-Pivot QuickSort | Cache-efficient, in-place |\n| Large arrays | Arrays.parallelSort | Utilizes multicore |\n| Top K elements | Min-Heap or QuickSelect | O(n log k) or O(n) |\n| Data > RAM | External Merge Sort | O(n log n) with disk I/O |\n| Multi-key sort | Stable sort + chained comparators | Preserves secondary order |\n| Nearly sorted | Insertion Sort or TimSort | O(n) best case |\n\n### Comparator Cheatsheet\n\n```java\n// Natural order\nComparator natural = Comparator.naturalOrder();\n\n// Reverse order\nComparator reverse = Comparator.reverseOrder();\n\n// By field\nComparator byAge = Comparator.comparingInt(Person::age);\nComparator byName = Comparator.comparing(Person::name);\n\n// Multiple fields\nComparator multi = Comparator\n .comparing(Person::lastName)\n .thenComparing(Person::firstName)\n .thenComparingInt(Person::age);\n\n// Null handling\nComparator nullsFirst = Comparator.nullsFirst(naturalOrder());\nComparator nullsLast = Comparator.nullsLast(naturalOrder());\n\n// Case insensitive\nComparator caseInsensitive = String.CASE_INSENSITIVE_ORDER;\n\n// Reversed\nComparator descAge = Comparator.comparingInt(Person::age).reversed();\n```\n\n### Stability Reference\n\n| Sort | Stable? | Notes |\n|------|---------|-------|\n| TimSort (objects) | Yes | Java's default for objects |\n| Dual-Pivot QuickSort | No | Java's default for primitives |\n| MergeSort | Yes | O(n) extra space |\n| HeapSort | No | In-place but unstable |\n| Insertion Sort | Yes | O(n²) but excellent for small/sorted |\n| Counting Sort | Yes | When implemented correctly |\n| Radix Sort (LSD) | Yes | Relies on stable digit sort |\n\n---\n\n## 📅 Review Schedule\n\n| Day | Focus | Time |\n|-----|-------|------|\n| Day 1 | Read full article, run code examples | 60 min |\n| Day 3 | Implement streaming top-K from scratch | 30 min |\n| Day 7 | Write Comparator for complex object | 20 min |\n| Day 14 | Debug the broken comparator exercise | 15 min |\n| Day 30 | Explain external sort to a colleague | 10 min |\n\n---\n\n## 🔗 What's Next?\n\n**Part 7: Advanced Sorting Techniques** covers:\n- IntroSort (QuickSort + HeapSort + Insertion)\n- Patience sorting and LIS connection\n- Sorting networks for parallel hardware\n- Adaptive algorithms for specific data patterns\n\n**Key insight preview**: Real-world sorting often combines multiple algorithms, adapting to data characteristics at runtime.\n\n---\n\n*This article is part of the Algorithms Compendium series. For the complete learning path, see Part 0: How to Use This Series.*\n","featuredImage","isPublished","isFeatured","subscriptionType","BASIC","publishedAt","2026-06-10T07:19:25.080684Z","createdAt","2026-06-10T07:19:25.081618Z","updatedAt","2026-06-16T21:26:56.086200Z","readingTimeMinutes",27,"estimatedReadingTime","authorId",3,"authorUsername","tomasz_main","categoryName","Algorithms","readingTime","seriesId",2,"seriesOrder",6,"author",{"_31":55,"_102":57,"_103":104,"_105":106,"_107":-5,"_108":-5,"_109":-5,"_110":-5,"_111":-5},"category",{"_31":64,"_73":59,"_35":99,"_76":100,"_101":-5},"tags",[79,80,81,82,83],"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":96,"_73":97,"_35":98},{"_31":93,"_73":94,"_35":95},{"_31":90,"_73":91,"_35":92},{"_31":87,"_73":88,"_35":89},{"_31":84,"_73":85,"_35":86},141,"Top-k","top-k",140,"Stability","stability",133,"Sorting","sorting",143,"External Sort","external-sort",142,"Comparator","comparator","algorithms","Category for Algorithms","colorHex","username","firstName","Tomasz","lastName","Jarosz","profilePicture","bio","website","githubUrl","linkedinUrl"]