[{"_1":2,"_3":-5,"_4":-5},"loaderData",{"_5":6},"actionData","errors","routes/blog-tag",{"_7":8,"_9":10},"tag",{"_31":87,"_73":88,"_35":89},"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",34,"title","Advanced Sorting Techniques","slug","algorithms-part-7-advanced-sorting-techniques","excerpt","Explore hybrid algorithms like IntroSort and TimSort, Patience Sort for nearly-sorted data, Block Sort for in-place stable sorting.","# Algorithms Compendium Part 7: Advanced Sorting Techniques\n\nThe algorithms from Parts 4-6 cover 95% of sorting needs. This article explores the remaining 5%: hybrid algorithms that combine multiple strategies, specialized sorts for specific data patterns, and parallel sorting architectures. These techniques appear in production-grade implementations like `std::sort` and custom high-performance systems.\n\n## 📋 At a Glance\n\n| Algorithm | Strategy | Best For |\n|-----------|----------|----------|\n| IntroSort | Quick + Heap + Insertion | General purpose (C++ std::sort) |\n| Patience Sort | Stack-based | Finding LIS, nearly-sorted data |\n| Block Sort | In-place stable merge | Memory-constrained stable sort |\n| Sorting Networks | Parallel comparisons | SIMD/GPU sorting |\n| TimSort | Run detection + merge | Adaptive (Java/Python default) |\n\n---\n\n## 🎯 What You'll Learn\n\nAfter reading this article, you will be able to:\n\n- **Implement IntroSort** - the hybrid behind C++ std::sort\n- **Understand Patience Sort** and its connection to Longest Increasing Subsequence\n- **Apply Block Sort** for in-place stable sorting\n- **Design sorting networks** for parallel execution\n- **Choose adaptive algorithms** based on data characteristics\n- **Benchmark and tune** hybrid sort parameters\n\n---\n\n## 🔥 Production Story: The Database Index Rebuild\n\nA financial database needed to rebuild indexes during low-traffic windows. The existing sort took 4 hours for 500 million records. The data had a specific pattern: mostly sorted with occasional out-of-order batches (from late-arriving transactions).\n\n```java\n// ❌ Initial approach: Standard QuickSort\npublic void rebuildIndex(long[] timestamps) {\n Arrays.sort(timestamps); // 4 hours\n}\n```\n\n**Analysis revealed:**\n- Data was 85% sorted (long runs of ascending values)\n- Out-of-order segments were small (10-50 elements)\n- QuickSort's O(n log n) didn't exploit the structure\n\n**The solution:**\n\n```java\n// ✅ Adaptive approach: Detect runs + targeted sorting\npublic void rebuildIndexAdaptive(long[] timestamps) {\n List runs = detectRuns(timestamps);\n\n // If highly sorted, use merge-based approach\n if (runs.size() < timestamps.length / 1000) {\n // Few runs = mostly sorted\n naturalMergeSort(timestamps, runs);\n } else {\n // Many runs = random order, use IntroSort\n introSort(timestamps, 0, timestamps.length - 1, maxDepth(timestamps.length));\n }\n}\n\n// Result: 45 minutes (5.3x faster!)\n```\n\n**Further optimization with TimSort principles:**\n\n```java\n// ✅ Full TimSort-style adaptive sort\npublic void rebuildIndexTimSort(long[] timestamps) {\n int minRun = computeMinRun(timestamps.length);\n List runs = new ArrayList<>();\n\n int i = 0;\n while (i < timestamps.length) {\n // Find natural run\n int runEnd = findRunEnd(timestamps, i);\n int runLen = runEnd - i;\n\n // Extend short runs with insertion sort\n if (runLen < minRun) {\n int forceEnd = Math.min(i + minRun, timestamps.length);\n insertionSort(timestamps, i, runEnd, forceEnd);\n runEnd = forceEnd;\n }\n\n runs.add(new RunDescriptor(i, runEnd - i));\n i = runEnd;\n\n // Merge runs according to invariants\n mergeCollapse(timestamps, runs);\n }\n\n // Final merge\n mergeForce(timestamps, runs);\n}\n\n// Result: 35 minutes (6.8x faster!)\n```\n\n**The lesson:** Understanding data characteristics enables algorithm selection that exploits structure. Production data is rarely random - adaptive algorithms turn \"noise\" into speed.\n\n---\n\n## 🧠 Mental Model: The Sorting Algorithm Zoo\n\n```text\nSORTING ALGORITHM CLASSIFICATION\n━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━\n\nBy Strategy:\n┌────────────────────────────────────────────────────────────┐\n│ COMPARISON-BASED │ NON-COMPARISON │\n│ ──────────────── │ ────────────── │\n│ QuickSort │ Counting Sort │\n│ MergeSort │ Radix Sort │\n│ HeapSort │ Bucket Sort │\n│ Insertion Sort │ │\n│ TimSort │ │\n└────────────────────────────────────────────────────────────┘\n\nBy Adaptivity:\n┌────────────────────────────────────────────────────────────┐\n│ NON-ADAPTIVE │ ADAPTIVE │\n│ ──────────── │ ──────── │\n│ HeapSort: always │ TimSort: O(n) on sorted │\n│ O(n log n) │ Insertion: O(n) on sorted │\n│ MergeSort: always │ IntroSort: switches strategy │\n│ O(n log n) │ SmoothSort: O(n) on sorted │\n└────────────────────────────────────────────────────────────┘\n\nBy Space Usage:\n┌────────────────────────────────────────────────────────────┐\n│ IN-PLACE O(1) │ EXTRA SPACE │\n│ ──────────── │ ─────────── │\n│ HeapSort │ MergeSort: O(n) │\n│ QuickSort: O(log n) │ TimSort: O(n) │\n│ Block Sort │ Counting: O(k) │\n│ Insertion Sort │ Radix: O(n+k) │\n└────────────────────────────────────────────────────────────┘\n```\n\n---\n\n## 🔬 Deep Dive: IntroSort\n\n### The Problem with QuickSort\n\nQuickSort has O(n²) worst case on already-sorted or adversarial input. While randomized pivot selection helps, it doesn't guarantee O(n log n).\n\n### IntroSort: The Hybrid Solution\n\nIntroSort (Introspective Sort) combines three algorithms:\n\n1. **QuickSort** - Fast average case, good cache behavior\n2. **HeapSort** - Guaranteed O(n log n) worst case\n3. **Insertion Sort** - Optimal for small subarrays\n\n```java\npublic class IntroSort {\n private static final int INSERTION_THRESHOLD = 16;\n\n /**\n * IntroSort: Hybrid of QuickSort, HeapSort, and Insertion Sort.\n * Time: O(n log n) guaranteed\n * Space: O(log n)\n */\n public static void sort(int[] arr) {\n if (arr == null || arr.length <= 1) return;\n\n // Max recursion depth: 2 * floor(log₂(n))\n int maxDepth = 2 * floorLog2(arr.length);\n introSort(arr, 0, arr.length - 1, maxDepth);\n }\n\n private static void introSort(int[] arr, int lo, int hi, int depthLimit) {\n int size = hi - lo + 1;\n\n // Base case: Use insertion sort for small subarrays\n if (size <= INSERTION_THRESHOLD) {\n insertionSort(arr, lo, hi);\n return;\n }\n\n // Depth exceeded: Switch to HeapSort to guarantee O(n log n)\n if (depthLimit == 0) {\n heapSort(arr, lo, hi);\n return;\n }\n\n // Normal case: QuickSort partition\n int pivot = medianOfThree(arr, lo, lo + size / 2, hi);\n int p = partition(arr, lo, hi, pivot);\n\n // Recurse on both partitions\n introSort(arr, lo, p - 1, depthLimit - 1);\n introSort(arr, p + 1, hi, depthLimit - 1);\n }\n\n /**\n * Median-of-three pivot selection.\n * Helps avoid worst case on sorted/reverse-sorted input.\n */\n private static int medianOfThree(int[] arr, int a, int b, int c) {\n if (arr[a] > arr[b]) {\n int tmp = arr[a]; arr[a] = arr[b]; arr[b] = tmp;\n }\n if (arr[b] > arr[c]) {\n int tmp = arr[b]; arr[b] = arr[c]; arr[c] = tmp;\n if (arr[a] > arr[b]) {\n tmp = arr[a]; arr[a] = arr[b]; arr[b] = tmp;\n }\n }\n return arr[b];\n }\n\n private static int partition(int[] arr, int lo, int hi, int pivot) {\n int i = lo;\n int j = hi;\n\n while (true) {\n while (arr[i] < pivot) i++;\n while (arr[j] > pivot) j--;\n\n if (i >= j) return j;\n\n int tmp = arr[i];\n arr[i] = arr[j];\n arr[j] = tmp;\n i++;\n j--;\n }\n }\n\n private static void insertionSort(int[] arr, int lo, int hi) {\n for (int i = lo + 1; i <= hi; i++) {\n int key = arr[i];\n int j = i - 1;\n\n while (j >= lo && arr[j] > key) {\n arr[j + 1] = arr[j];\n j--;\n }\n arr[j + 1] = key;\n }\n }\n\n private static void heapSort(int[] arr, int lo, int hi) {\n int n = hi - lo + 1;\n\n // Build max heap\n for (int i = n / 2 - 1; i >= 0; i--) {\n heapify(arr, lo, n, i);\n }\n\n // Extract elements from heap\n for (int i = n - 1; i > 0; i--) {\n // Move root to end\n int tmp = arr[lo];\n arr[lo] = arr[lo + i];\n arr[lo + i] = tmp;\n\n // Heapify reduced heap\n heapify(arr, lo, i, 0);\n }\n }\n\n private static void heapify(int[] arr, int lo, 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[lo + left] > arr[lo + largest]) {\n largest = left;\n }\n if (right < n && arr[lo + right] > arr[lo + largest]) {\n largest = right;\n }\n\n if (largest != i) {\n int tmp = arr[lo + i];\n arr[lo + i] = arr[lo + largest];\n arr[lo + largest] = tmp;\n heapify(arr, lo, n, largest);\n }\n }\n\n private static int floorLog2(int n) {\n return 31 - Integer.numberOfLeadingZeros(n);\n }\n}\n```\n\n### IntroSort Analysis\n\n| Phase | Condition | Algorithm | Rationale |\n|-------|-----------|-----------|-----------|\n| Normal | size > 16, depth > 0 | QuickSort | Fast average case |\n| Small | size ≤ 16 | Insertion Sort | Low overhead, cache-friendly |\n| Deep | depth = 0 | HeapSort | Guarantee O(n log n) |\n\n**Why 16 for insertion threshold?**\n- QuickSort overhead (function calls, partition) exceeds insertion sort for small n\n- 16 is empirically optimal for most architectures\n- Cache lines typically hold 16 integers (64 bytes / 4 bytes)\n\n**Why 2·log₂(n) for depth limit?**\n- QuickSort with good pivots has depth log₂(n)\n- 2× factor allows for some bad pivots before switching\n- Beyond 2·log₂(n) suggests adversarial input or very bad luck\n\n---\n\n## 🔬 Deep Dive: Patience Sort\n\n### The Card Game Connection\n\nPatience Sort comes from the card game Patience (Solitaire). The algorithm places cards on piles following a rule, and the number of piles equals the Longest Increasing Subsequence length.\n\n### The Algorithm\n\n```java\npublic class PatienceSort {\n /**\n * Patience Sort using TreeMap for O(n log n) pile finding.\n * Time: O(n log n)\n * Space: O(n)\n */\n public static void sort(int[] arr) {\n if (arr == null || arr.length <= 1) return;\n\n // Each pile is a stack (only top matters for placement)\n List> piles = new ArrayList<>();\n\n // TreeMap maps pile top -> pile index (for binary search)\n TreeMap pileIndex = new TreeMap<>();\n\n for (int card : arr) {\n // Find leftmost pile with top >= card\n Map.Entry entry = pileIndex.ceilingEntry(card);\n\n if (entry == null) {\n // No suitable pile - create new one\n int newPileIdx = piles.size();\n Deque newPile = new ArrayDeque<>();\n newPile.push(card);\n piles.add(newPile);\n pileIndex.put(card, newPileIdx);\n } else {\n // Place on existing pile\n int pileIdx = entry.getValue();\n Deque pile = piles.get(pileIdx);\n\n // Remove old top from index\n pileIndex.remove(pile.peek());\n\n // Add card and update index\n pile.push(card);\n pileIndex.put(card, pileIdx);\n }\n }\n\n // Merge piles using k-way merge\n kWayMerge(piles, arr);\n }\n\n /**\n * K-way merge of piles into sorted array.\n */\n private static void kWayMerge(List> piles, int[] result) {\n PriorityQueue pq = new PriorityQueue<>(\n Comparator.comparingInt(p -> p.value)\n );\n\n // Initialize with bottom of each pile\n for (int i = 0; i < piles.size(); i++) {\n Deque pile = piles.get(i);\n if (!pile.isEmpty()) {\n // We need bottom-to-top, so reverse\n List reversed = new ArrayList<>();\n while (!pile.isEmpty()) {\n reversed.add(pile.pop());\n }\n Collections.reverse(reversed);\n\n pq.offer(new PilePointer(i, 0, reversed.get(0), reversed));\n }\n }\n\n // Extract in order\n int idx = 0;\n while (!pq.isEmpty()) {\n PilePointer min = pq.poll();\n result[idx++] = min.value;\n\n // Advance pointer\n if (min.index + 1 < min.pile.size()) {\n pq.offer(new PilePointer(\n min.pileNum,\n min.index + 1,\n min.pile.get(min.index + 1),\n min.pile\n ));\n }\n }\n }\n\n private record PilePointer(int pileNum, int index, int value, List pile) {}\n}\n```\n\n### Patience Sort and LIS\n\nThe number of piles after placing all cards equals the LIS length:\n\n```java\npublic class LongestIncreasingSubsequence {\n /**\n * Find LIS length using Patience Sort principle.\n * Time: O(n log n)\n * Space: O(n)\n */\n public static int lisLength(int[] arr) {\n if (arr == null || arr.length == 0) return 0;\n\n // pileTops[i] = smallest top value among piles of height i+1\n List pileTops = new ArrayList<>();\n\n for (int num : arr) {\n int pos = Collections.binarySearch(pileTops, num);\n\n if (pos < 0) {\n pos = -(pos + 1); // Insertion point\n }\n\n if (pos == pileTops.size()) {\n pileTops.add(num); // New pile\n } else {\n pileTops.set(pos, num); // Replace top\n }\n }\n\n return pileTops.size();\n }\n\n /**\n * Find actual LIS (not just length) using backpointers.\n */\n public static List lis(int[] arr) {\n if (arr == null || arr.length == 0) return Collections.emptyList();\n\n int n = arr.length;\n List pileTops = new ArrayList<>();\n int[] pileAssignment = new int[n]; // Which pile each element went to\n int[] predecessor = new int[n]; // Previous element in LIS\n\n Arrays.fill(predecessor, -1);\n int[] pileTop = new int[n]; // Index of top element in each pile\n\n for (int i = 0; i < n; i++) {\n int pos = Collections.binarySearch(pileTops, arr[i]);\n\n if (pos < 0) {\n pos = -(pos + 1);\n }\n\n if (pos == pileTops.size()) {\n pileTops.add(arr[i]);\n } else {\n pileTops.set(pos, arr[i]);\n }\n\n pileAssignment[i] = pos;\n pileTop[pos] = i;\n\n if (pos > 0) {\n predecessor[i] = pileTop[pos - 1];\n }\n }\n\n // Reconstruct LIS\n List result = new ArrayList<>();\n int idx = pileTop[pileTops.size() - 1];\n\n while (idx != -1) {\n result.add(arr[idx]);\n idx = predecessor[idx];\n }\n\n Collections.reverse(result);\n return result;\n }\n}\n```\n\n### When to Use Patience Sort\n\n| Scenario | Patience Sort vs Others |\n|----------|------------------------|\n| Need LIS | Perfect - O(n log n) |\n| Nearly sorted | Good - few piles, fast merge |\n| Random data | Similar to MergeSort |\n| Memory constrained | Not ideal - O(n) space |\n\n---\n\n## 🔬 Deep Dive: Block Sort (WikiSort)\n\n### The Challenge: In-Place Stable Merge\n\nMergeSort is stable but requires O(n) extra space. Can we achieve stable O(n log n) sorting with O(1) extra space?\n\n### Block Sort Approach\n\nBlock Sort (also known as WikiSort) achieves in-place stable merge through clever block manipulation:\n\n```java\npublic class BlockSort {\n private static final int BLOCK_SIZE = 512;\n\n /**\n * Block Sort: In-place stable sort.\n * Time: O(n log n)\n * Space: O(1)\n */\n public static void sort(int[] arr) {\n if (arr == null || arr.length <= 1) return;\n\n int n = arr.length;\n\n // Step 1: Sort small blocks with insertion sort\n for (int i = 0; i < n; i += BLOCK_SIZE) {\n int end = Math.min(i + BLOCK_SIZE, n);\n insertionSort(arr, i, end - 1);\n }\n\n // Step 2: Merge sorted blocks, doubling size each iteration\n for (int width = BLOCK_SIZE; width < n; width *= 2) {\n for (int i = 0; i < n; i += 2 * width) {\n int mid = Math.min(i + width, n);\n int end = Math.min(i + 2 * width, n);\n\n if (mid < end) {\n inPlaceMerge(arr, i, mid, end);\n }\n }\n }\n }\n\n /**\n * In-place merge of arr[lo..mid) and arr[mid..hi).\n * Uses rotation to achieve stability without extra space.\n */\n private static void inPlaceMerge(int[] arr, int lo, int mid, int hi) {\n if (lo >= mid || mid >= hi) return;\n\n // Already sorted?\n if (arr[mid - 1] <= arr[mid]) return;\n\n while (lo < mid && mid < hi) {\n // Find where arr[mid] should go in left half\n int insertPos = upperBound(arr, lo, mid, arr[mid]);\n\n if (insertPos == mid) {\n // Left half element stays in place\n lo++;\n } else {\n // Rotate arr[insertPos..mid..mid+1] to bring arr[mid] into position\n int rotateCount = mid - insertPos;\n rotate(arr, insertPos, mid, mid + 1);\n lo = insertPos + 1;\n mid++;\n }\n }\n }\n\n /**\n * Rotate arr[lo..mid..hi) so that arr[mid..hi) comes before arr[lo..mid).\n */\n private static void rotate(int[] arr, int lo, int mid, int hi) {\n reverse(arr, lo, mid);\n reverse(arr, mid, hi);\n reverse(arr, lo, hi);\n }\n\n private static void reverse(int[] arr, int lo, int hi) {\n hi--;\n while (lo < hi) {\n int tmp = arr[lo];\n arr[lo] = arr[hi];\n arr[hi] = tmp;\n lo++;\n hi--;\n }\n }\n\n private static int upperBound(int[] arr, int lo, int hi, int value) {\n while (lo < hi) {\n int mid = lo + (hi - lo) / 2;\n if (arr[mid] <= value) {\n lo = mid + 1;\n } else {\n hi = mid;\n }\n }\n return lo;\n }\n\n private static void insertionSort(int[] arr, int lo, int hi) {\n for (int i = lo + 1; i <= hi; i++) {\n int key = arr[i];\n int j = i - 1;\n while (j >= lo && arr[j] > key) {\n arr[j + 1] = arr[j];\n j--;\n }\n arr[j + 1] = key;\n }\n }\n}\n```\n\n### Block Sort Characteristics\n\n| Property | Value |\n|----------|-------|\n| Time | O(n log n) |\n| Space | O(1) - truly in-place |\n| Stable | Yes |\n| Adaptive | Partially - uses existing order in merge |\n\n**Trade-off**: The constant factor is higher than standard MergeSort due to rotation overhead.\n\n---\n\n## 🔬 Deep Dive: Sorting Networks\n\n### What is a Sorting Network?\n\nA sorting network is a fixed sequence of comparators that sorts any input of a given size. Unlike comparison sorts that adapt to input, sorting networks perform the same comparisons regardless of data.\n\n```text\nSORTING NETWORK FOR 4 ELEMENTS\n━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━\n\nInput: 3 1 4 2\n │ │ │ │\n ├──┼──┤ │ Compare-swap (0,2)\n │ │ │ │\n │ ├──┼──┤ Compare-swap (1,3)\n │ │ │ │\n ├──┤ ├──┤ Compare-swap (0,1), (2,3)\n │ │ │ │\n │ ├──┤ │ Compare-swap (1,2)\n │ │ │ │\nOutput: 1 2 3 4\n```\n\n### Bitonic Sort\n\nBitonic Sort is a parallel sorting network algorithm:\n\n```java\npublic class BitonicSort {\n /**\n * Bitonic Sort - sorting network suitable for parallel execution.\n * Time: O(n log² n) comparisons\n * Parallel time: O(log² n) with O(n) processors\n */\n public static void sort(int[] arr) {\n if (arr == null || arr.length <= 1) return;\n\n // Pad to power of 2 if necessary\n int n = nextPowerOfTwo(arr.length);\n int[] padded = Arrays.copyOf(arr, n);\n Arrays.fill(padded, arr.length, n, Integer.MAX_VALUE);\n\n bitonicSort(padded, 0, n, true);\n\n // Copy back\n System.arraycopy(padded, 0, arr, 0, arr.length);\n }\n\n /**\n * Recursively sort a bitonic sequence.\n * @param ascending true for ascending, false for descending\n */\n private static void bitonicSort(int[] arr, int lo, int count, boolean ascending) {\n if (count <= 1) return;\n\n int half = count / 2;\n\n // Sort first half ascending, second half descending\n // This creates a bitonic sequence\n bitonicSort(arr, lo, half, true);\n bitonicSort(arr, lo + half, half, false);\n\n // Merge the bitonic sequence\n bitonicMerge(arr, lo, count, ascending);\n }\n\n /**\n * Merge a bitonic sequence into sorted order.\n */\n private static void bitonicMerge(int[] arr, int lo, int count, boolean ascending) {\n if (count <= 1) return;\n\n int half = count / 2;\n\n // Compare-swap pairs that are 'half' apart\n for (int i = lo; i < lo + half; i++) {\n compareSwap(arr, i, i + half, ascending);\n }\n\n // Recursively merge both halves\n bitonicMerge(arr, lo, half, ascending);\n bitonicMerge(arr, lo + half, half, ascending);\n }\n\n private static void compareSwap(int[] arr, int i, int j, boolean ascending) {\n boolean swap = ascending ? (arr[i] > arr[j]) : (arr[i] < arr[j]);\n if (swap) {\n int tmp = arr[i];\n arr[i] = arr[j];\n arr[j] = tmp;\n }\n }\n\n private static int nextPowerOfTwo(int n) {\n return Integer.highestOneBit(n - 1) << 1;\n }\n}\n```\n\n### Parallel Bitonic Sort with Fork/Join\n\n```java\npublic class ParallelBitonicSort {\n private static final int THRESHOLD = 1024;\n\n public static void sort(int[] arr) {\n int n = nextPowerOfTwo(arr.length);\n int[] padded = Arrays.copyOf(arr, n);\n Arrays.fill(padded, arr.length, n, Integer.MAX_VALUE);\n\n ForkJoinPool pool = ForkJoinPool.commonPool();\n pool.invoke(new BitonicTask(padded, 0, n, true, true));\n\n System.arraycopy(padded, 0, arr, 0, arr.length);\n }\n\n private static class BitonicTask extends RecursiveAction {\n private final int[] arr;\n private final int lo, count;\n private final boolean ascending;\n private final boolean sortPhase; // true = sort, false = merge\n\n BitonicTask(int[] arr, int lo, int count, boolean ascending, boolean sortPhase) {\n this.arr = arr;\n this.lo = lo;\n this.count = count;\n this.ascending = ascending;\n this.sortPhase = sortPhase;\n }\n\n @Override\n protected void compute() {\n if (count <= THRESHOLD) {\n if (sortPhase) {\n sequentialBitonicSort(arr, lo, count, ascending);\n } else {\n sequentialBitonicMerge(arr, lo, count, ascending);\n }\n return;\n }\n\n int half = count / 2;\n\n if (sortPhase) {\n // Sort phase: sort halves in opposite directions, then merge\n BitonicTask left = new BitonicTask(arr, lo, half, true, true);\n BitonicTask right = new BitonicTask(arr, lo + half, half, false, true);\n\n invokeAll(left, right);\n\n // Now merge the bitonic sequence\n new BitonicTask(arr, lo, count, ascending, false).compute();\n } else {\n // Merge phase: compare-swap, then merge halves\n for (int i = lo; i < lo + half; i++) {\n boolean swap = ascending ? (arr[i] > arr[i + half]) : (arr[i] < arr[i + half]);\n if (swap) {\n int tmp = arr[i];\n arr[i] = arr[i + half];\n arr[i + half] = tmp;\n }\n }\n\n BitonicTask left = new BitonicTask(arr, lo, half, ascending, false);\n BitonicTask right = new BitonicTask(arr, lo + half, half, ascending, false);\n\n invokeAll(left, right);\n }\n }\n\n private void sequentialBitonicSort(int[] arr, int lo, int count, boolean asc) {\n if (count <= 1) return;\n int half = count / 2;\n sequentialBitonicSort(arr, lo, half, true);\n sequentialBitonicSort(arr, lo + half, half, false);\n sequentialBitonicMerge(arr, lo, count, asc);\n }\n\n private void sequentialBitonicMerge(int[] arr, int lo, int count, boolean asc) {\n if (count <= 1) return;\n int half = count / 2;\n for (int i = lo; i < lo + half; i++) {\n boolean swap = asc ? (arr[i] > arr[i + half]) : (arr[i] < arr[i + half]);\n if (swap) {\n int tmp = arr[i];\n arr[i] = arr[i + half];\n arr[i + half] = tmp;\n }\n }\n sequentialBitonicMerge(arr, lo, half, asc);\n sequentialBitonicMerge(arr, lo + half, half, asc);\n }\n }\n\n private static int nextPowerOfTwo(int n) {\n return Integer.highestOneBit(n - 1) << 1;\n }\n}\n```\n\n### Sorting Networks: When to Use\n\n| Use Case | Benefit |\n|----------|---------|\n| SIMD sorting | Compare-swap maps to vector instructions |\n| GPU sorting | Predictable memory access, no branches |\n| Hardware sorting | Fixed circuit, no control flow |\n| Small fixed-size sorts | Optimal for n ≤ 16 |\n\n---\n\n## 🔬 Deep Dive: Adaptive Algorithms\n\n### SmoothSort\n\nSmoothSort is a HeapSort variant that achieves O(n) on sorted input:\n\n```java\npublic class SmoothSort {\n // Leonardo numbers: L(n) = L(n-1) + L(n-2) + 1\n private static final int[] LEONARDO = computeLeonardo();\n\n private static int[] computeLeonardo() {\n int[] leo = new int[46]; // Enough for int range\n leo[0] = 1;\n leo[1] = 1;\n for (int i = 2; i < leo.length; i++) {\n leo[i] = leo[i-1] + leo[i-2] + 1;\n }\n return leo;\n }\n\n /**\n * SmoothSort: HeapSort variant that's O(n) on sorted input.\n * Time: O(n log n) worst, O(n) best\n * Space: O(1)\n */\n public static void sort(int[] arr) {\n if (arr == null || arr.length <= 1) return;\n\n int n = arr.length;\n\n // Build Leonardo heap\n int p = 0; // Bit vector of tree sizes (Leonardo numbers)\n int q = 0; // Smallest tree size index\n\n for (int i = 0; i < n; i++) {\n if ((p & 3) == 3) {\n // Combine two smallest trees\n sift(arr, i, q);\n p = (p >> 2) | 1;\n q += 2;\n } else if (q == 1 && (p & 1) == 1) {\n // Add L(1) tree\n sift(arr, i, q);\n p = (p >> 1) | 1;\n q--;\n } else if (q >= 2) {\n // Add L(q-1) tree\n sift(arr, i, q - 1);\n p = (p << (q - 1)) | 1;\n q = 1;\n } else {\n // Add L(1) tree\n sift(arr, i, 1);\n p = (p << 1) | 1;\n q = 0;\n }\n\n // Restore heap property between roots\n restoreRoots(arr, i, p, q);\n }\n\n // Extract elements\n for (int i = n - 1; i > 0; i--) {\n if (q <= 1) {\n p >>= 1;\n q++;\n while ((p & 1) == 0 && p != 0) {\n p >>= 1;\n q++;\n }\n } else {\n // Split tree into two children\n p = (p & ~1) | (3 << (q - 2));\n q -= 2;\n\n // Restore both children\n int right = i - 1;\n int left = right - LEONARDO[q + 1];\n restoreRoots(arr, left, p >> 1, q + 1);\n restoreRoots(arr, right, p, q);\n }\n }\n }\n\n private static void sift(int[] arr, int root, int size) {\n while (size >= 2) {\n int right = root - 1;\n int left = right - LEONARDO[size - 2];\n int largest = root;\n\n if (arr[left] > arr[largest]) largest = left;\n if (arr[right] > arr[largest]) largest = right;\n\n if (largest == root) break;\n\n int tmp = arr[root];\n arr[root] = arr[largest];\n arr[largest] = tmp;\n\n root = largest;\n size = (largest == left) ? size - 1 : size - 2;\n }\n }\n\n private static void restoreRoots(int[] arr, int i, int p, int q) {\n while (p > 1) {\n int prevRoot = i - LEONARDO[q];\n if (arr[prevRoot] <= arr[i]) break;\n\n // Check if current root has children that are larger\n if (q >= 2) {\n int right = i - 1;\n int left = right - LEONARDO[q - 2];\n if (arr[left] > arr[prevRoot] || arr[right] > arr[prevRoot]) {\n break;\n }\n }\n\n // Swap with previous root\n int tmp = arr[i];\n arr[i] = arr[prevRoot];\n arr[prevRoot] = tmp;\n\n i = prevRoot;\n\n // Move to next smaller tree\n do {\n p >>= 1;\n q++;\n } while ((p & 1) == 0);\n }\n }\n}\n```\n\n### Natural Merge Sort\n\nNatural MergeSort exploits existing sorted runs:\n\n```java\npublic class NaturalMergeSort {\n /**\n * Natural MergeSort: Exploits existing sorted runs.\n * Time: O(n log n) worst, O(n) on sorted input\n * Space: O(n)\n */\n public static void sort(int[] arr) {\n if (arr == null || arr.length <= 1) return;\n\n int n = arr.length;\n int[] aux = new int[n];\n\n // Merge until single run\n while (true) {\n int runCount = 0;\n int i = 0;\n\n while (i < n) {\n // Find first run\n int runStart = i;\n while (i < n - 1 && arr[i] <= arr[i + 1]) i++;\n int runMid = ++i;\n\n if (i >= n) {\n runCount++;\n break;\n }\n\n // Find second run\n while (i < n - 1 && arr[i] <= arr[i + 1]) i++;\n int runEnd = ++i;\n\n // Merge the two runs\n merge(arr, aux, runStart, runMid, runEnd);\n runCount++;\n }\n\n if (runCount <= 1) break;\n }\n }\n\n private static void merge(int[] arr, int[] aux, int lo, int mid, int hi) {\n // Copy to aux\n System.arraycopy(arr, lo, aux, lo, hi - lo);\n\n int i = lo, j = mid, k = lo;\n\n while (i < mid && j < hi) {\n if (aux[i] <= aux[j]) {\n arr[k++] = aux[i++];\n } else {\n arr[k++] = aux[j++];\n }\n }\n\n while (i < mid) arr[k++] = aux[i++];\n // j elements already in place\n }\n}\n```\n\n---\n\n## ⚠️ Common Mistakes\n\n### Mistake 1: Wrong IntroSort Depth Limit\n\n```java\n// ❌ Depth limit too small - switches to HeapSort too early\nint maxDepth = floorLog2(n); // Should be 2 * floorLog2(n)\n\n// ❌ Depth limit too large - defeats the purpose\nint maxDepth = n; // Will never switch to HeapSort\n```\n\n### Mistake 2: Not Handling Power-of-Two Requirement\n\n```java\n// ❌ Bitonic sort on non-power-of-two length crashes\nint[] arr = new int[100];\nbitonicSort(arr, 0, arr.length, true); // IndexOutOfBoundsException!\n\n// ✅ Pad to next power of two\nint n = Integer.highestOneBit(arr.length - 1) << 1;\nint[] padded = Arrays.copyOf(arr, n);\nArrays.fill(padded, arr.length, n, Integer.MAX_VALUE);\n```\n\n### Mistake 3: Rotation in Block Sort Destroys Stability\n\n```java\n// ❌ Wrong rotation direction breaks stability\nprivate static void rotate(int[] arr, int lo, int mid, int hi) {\n // Rotating wrong way!\n reverse(arr, mid, hi); // Should be first\n reverse(arr, lo, mid); // Should be second\n reverse(arr, lo, hi);\n}\n```\n\n### Mistake 4: Threshold Too Low for Hybrid Sorts\n\n```java\n// ❌ Switching to insertion sort at size 4 wastes QuickSort efficiency\nprivate static final int INSERTION_THRESHOLD = 4;\n\n// ✅ Empirical optimal is usually 16-32\nprivate static final int INSERTION_THRESHOLD = 16;\n```\n\n---\n\n## 🐛 Debug This: The Broken IntroSort\n\nThis IntroSort has several bugs. Find and fix them:\n\n```java\npublic class BrokenIntroSort {\n private static final int THRESHOLD = 16;\n\n public static void sort(int[] arr) {\n int maxDepth = (int)(Math.log(arr.length)); // Bug 1\n introSort(arr, 0, arr.length, maxDepth); // Bug 2\n }\n\n private static void introSort(int[] arr, int lo, int hi, int depth) {\n if (hi - lo < THRESHOLD) {\n insertionSort(arr, lo, hi);\n return;\n }\n\n if (depth == 0) {\n heapSort(arr, lo, hi);\n return;\n }\n\n int pivot = arr[lo]; // Bug 3\n int p = partition(arr, lo, hi, pivot);\n\n introSort(arr, lo, p, depth--); // Bug 4\n introSort(arr, p + 1, hi, depth);\n }\n\n private static int partition(int[] arr, int lo, int hi, int pivot) {\n int i = lo;\n int j = hi; // Bug 5\n\n while (i < j) {\n while (arr[i] < pivot) i++;\n while (arr[j] > pivot) j--;\n\n if (i <= j) {\n int tmp = arr[i];\n arr[i] = arr[j];\n arr[j] = tmp;\n i++;\n j--;\n }\n }\n return i;\n }\n\n private static void insertionSort(int[] arr, int lo, int hi) {\n for (int i = lo + 1; i < hi; i++) { // Bug 6\n int key = arr[i];\n int j = i - 1;\n while (j >= lo && arr[j] > key) {\n arr[j + 1] = arr[j];\n j--;\n }\n arr[j + 1] = key;\n }\n }\n\n private static void heapSort(int[] arr, int lo, int hi) {\n // Assume correct implementation\n }\n}\n```\n\n

💡 Hint

\n\nLook for:\n1. Math function choice for depth\n2. Inclusive vs exclusive bounds\n3. Pivot selection strategy\n4. Pre vs post decrement\n5. Array bounds\n6. Loop bounds consistency\n\n

\n\n

✅ Solution

\n\n```java\npublic class FixedIntroSort {\n private static final int THRESHOLD = 16;\n\n public static void sort(int[] arr) {\n if (arr == null || arr.length <= 1) return;\n\n // ✅ Fix 1: Use log base 2, multiply by 2\n // Math.log is natural log, not log2!\n int maxDepth = 2 * (31 - Integer.numberOfLeadingZeros(arr.length));\n introSort(arr, 0, arr.length - 1, maxDepth); // ✅ Fix 2: Use inclusive hi\n }\n\n private static void introSort(int[] arr, int lo, int hi, int depth) {\n int size = hi - lo + 1; // Adjusted for inclusive bounds\n\n if (size <= THRESHOLD) {\n insertionSort(arr, lo, hi);\n return;\n }\n\n if (depth == 0) {\n heapSort(arr, lo, hi);\n return;\n }\n\n // ✅ Fix 3: Use median-of-three pivot\n int mid = lo + (hi - lo) / 2;\n int pivot = medianOfThree(arr, lo, mid, hi);\n int p = partition(arr, lo, hi, pivot);\n\n // ✅ Fix 4: Use depth - 1, not depth--\n introSort(arr, lo, p - 1, depth - 1);\n introSort(arr, p + 1, hi, depth - 1);\n }\n\n private static int medianOfThree(int[] arr, int a, int b, int c) {\n if (arr[a] > arr[b]) swap(arr, a, b);\n if (arr[b] > arr[c]) swap(arr, b, c);\n if (arr[a] > arr[b]) swap(arr, a, b);\n return arr[b];\n }\n\n private static int partition(int[] arr, int lo, int hi, int pivot) {\n int i = lo;\n int j = hi; // ✅ Fix 5: With inclusive bounds, this is correct\n\n while (true) {\n while (arr[i] < pivot) i++;\n while (arr[j] > pivot) j--;\n\n if (i >= j) return j;\n\n swap(arr, i, j);\n i++;\n j--;\n }\n }\n\n private static void insertionSort(int[] arr, int lo, int hi) {\n // ✅ Fix 6: Use <= for inclusive bounds\n for (int i = lo + 1; i <= hi; i++) {\n int key = arr[i];\n int j = i - 1;\n while (j >= lo && arr[j] > key) {\n arr[j + 1] = arr[j];\n j--;\n }\n arr[j + 1] = key;\n }\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 heapSort(int[] arr, int lo, int hi) {\n // Implementation as before\n }\n}\n```\n\n**Bugs explained:**\n\n1. **Math.log returns natural log**: `Math.log(n)` is ln(n), not log₂(n). For n=1000, this gives 6.9 instead of 10.\n\n2. **Exclusive vs inclusive bounds**: The original used exclusive hi (like Arrays indices), but partition logic assumed inclusive.\n\n3. **First element pivot**: Using arr[lo] as pivot causes O(n²) on sorted input - the exact case IntroSort should avoid.\n\n4. **Post-decrement depth**: `depth--` returns the old value, so both recursive calls get the same depth. Use `depth - 1`.\n\n5. **Partition bounds**: With exclusive hi, `arr[hi]` is out of bounds.\n\n6. **Loop bounds mismatch**: insertionSort used `< hi` while rest of code used inclusive bounds.\n\n

\n\n---\n\n## 💻 Exercises\n\n### Exercise 1: IntroSort with 3-Way Partitioning ⭐⭐\n\nExtend IntroSort to use 3-way partitioning for arrays with many duplicates.\n\n```java\npublic class IntroSort3Way {\n /**\n * IntroSort with 3-way partitioning for arrays with duplicates.\n * Returns [lt, gt] where:\n * - arr[lo..lt) < pivot\n * - arr[lt..gt] == pivot\n * - arr(gt..hi] > pivot\n */\n public static void sort(int[] arr) {\n // Your implementation\n }\n}\n```\n\n---\n\n### Exercise 2: Patience Sort with LIS Reconstruction ⭐⭐\n\nImplement Patience Sort that also returns the LIS itself, not just sorted array.\n\n```java\npublic class PatienceSortWithLIS {\n public record SortResult(int[] sorted, List lis) {}\n\n /**\n * Sort array and return both sorted result and LIS.\n */\n public static SortResult sort(int[] arr) {\n // Your implementation\n }\n}\n```\n\n---\n\n### Exercise 3: Parallel Odd-Even Sort ⭐⭐⭐\n\nImplement Odd-Even Transposition Sort - another sorting network suitable for parallel execution.\n\n```java\npublic class OddEvenSort {\n /**\n * Odd-Even Sort: Simple sorting network.\n * Alternates between comparing odd-even and even-odd pairs.\n * Time: O(n²) sequential, O(n) parallel with O(n) processors\n */\n public static void sort(int[] arr) {\n // Your implementation\n }\n\n /**\n * Parallel version using Fork/Join.\n */\n public static void parallelSort(int[] arr) {\n // Your implementation\n }\n}\n```\n\n---\n\n### Exercise 4: Run-Aware Natural MergeSort ⭐⭐⭐\n\nImplement a MergeSort that:\n1. Detects both ascending AND descending runs\n2. Reverses descending runs in-place\n3. Merges using galloping (like TimSort)\n\n```java\npublic class RunAwareMergeSort {\n /**\n * Natural MergeSort with descending run detection and galloping.\n */\n public static void sort(int[] arr) {\n // Your implementation\n }\n}\n```\n\n

💡 Hint

\n\nGalloping: When merging and one run is \"winning\" consistently, binary search to find where the other run's next element should go, then copy a chunk at once.\n\n

\n\n---\n\n### Exercise 5: Adaptive Algorithm Selector ⭐⭐⭐⭐\n\nCreate a sorting system that automatically selects the best algorithm based on data analysis.\n\n```java\npublic class AdaptiveSorter {\n public enum Algorithm {\n INSERTION, QUICK, MERGE, HEAP, COUNTING, RADIX\n }\n\n /**\n * Analyze data and select best algorithm.\n */\n public static Algorithm selectAlgorithm(int[] arr) {\n // Analyze: size, sortedness, range, distribution\n // Return optimal algorithm\n }\n\n /**\n * Sort using automatically selected algorithm.\n */\n public static void sort(int[] arr) {\n Algorithm algo = selectAlgorithm(arr);\n switch (algo) {\n case INSERTION -> insertionSort(arr);\n case QUICK -> quickSort(arr);\n case MERGE -> mergeSort(arr);\n case HEAP -> heapSort(arr);\n case COUNTING -> countingSort(arr);\n case RADIX -> radixSort(arr);\n }\n }\n}\n```\n\n---\n\n## 🎤 Interview Questions\n\n### Question 1: Why does C++ std::sort use IntroSort instead of pure QuickSort?\n\n**Answer:**\n\nPure QuickSort has O(n²) worst case on:\n- Already sorted input\n- Reverse sorted input\n- All equal elements\n- Adversarial input (killer sequences)\n\nIntroSort solves this by monitoring recursion depth. If depth exceeds 2·log₂(n), it switches to HeapSort which guarantees O(n log n).\n\n**Additional optimizations in std::sort:**\n1. Median-of-three pivot selection reduces bad pivot probability\n2. Insertion sort for small subarrays (typically n < 16) reduces overhead\n3. Some implementations use median-of-medians for guaranteed O(n log n) pivot\n\nThe combination achieves:\n- **Average case**: QuickSort's excellent cache performance\n- **Worst case**: HeapSort's O(n log n) guarantee\n- **Small arrays**: Insertion sort's low overhead\n\n---\n\n### Question 2: Explain how TimSort achieves O(n) on sorted input\n\n**Answer:**\n\nTimSort's key insight: real-world data often has sorted \"runs.\"\n\n**Phase 1 - Run detection:**\n```text\nInput: [1, 2, 3, 4, 10, 9, 8, 5, 6, 7]\n └──run 1──┘ └─run 2─┘ └run 3┘\n```\n- Scans for natural ascending/descending runs\n- Descending runs are reversed in-place\n\n**Phase 2 - Run extension:**\n- If run < minRun (typically 32-64), extend with insertion sort\n- Insertion sort is O(n²) but O(n) on nearly-sorted data\n\n**Phase 3 - Merge:**\n- Merge runs according to invariants that keep the stack balanced\n- Uses galloping mode: when one run \"wins\" 7+ times, binary search ahead\n\n**On sorted input:**\n- Single run detected in O(n) scan\n- No merging needed\n- Total: O(n)\n\n**On reverse-sorted input:**\n- Single descending run detected in O(n)\n- Reverse in O(n)\n- Total: O(n)\n\n---\n\n### Question 3: When would you use a sorting network over comparison sort?\n\n**Answer:**\n\nSorting networks excel when:\n\n1. **SIMD/Vector processing**: Compare-swap maps directly to vector instructions. Can compare 4-8 pairs simultaneously.\n\n2. **GPU sorting**: Predictable memory access patterns, no branch divergence. Bitonic sort is popular for GPU.\n\n3. **Hardware implementation**: Fixed circuit, no control flow logic needed.\n\n4. **Real-time systems**: Constant execution time regardless of input (no worst case variation).\n\n5. **Small fixed-size sorts**: Optimal networks exist for small n. For n=4, only 5 comparisons needed.\n\n**Drawbacks:**\n- O(n log² n) for Bitonic vs O(n log n) for comparison sorts\n- Requires power-of-two size (or padding)\n- Not adaptive - same comparisons regardless of input\n\n**Example use**: Sorting network for fixed-size median filter in image processing:\n```java\n// 5-element median using sorting network\nint median5(int a, int b, int c, int d, int e) {\n // 6 compare-swaps, always same pattern\n if (a > b) { int t = a; a = b; b = t; }\n if (d > e) { int t = d; d = e; e = t; }\n if (a > c) { int t = a; a = c; c = t; }\n if (b > c) { int t = b; b = c; c = t; }\n if (a > d) { int t = a; a = d; d = t; }\n if (c > d) { int t = c; c = d; d = t; }\n return c; // Third element is median\n}\n```\n\n---\n\n### Question 4: How would you sort streaming data with limited memory?\n\n**Answer:**\n\nFor streaming data where you can't store everything:\n\n**Approach 1: External Sort with Bounded Memory**\n```java\n// Process in chunks\nwhile (hasMoreInput()) {\n List chunk = readChunk(maxMemory / 2);\n Collections.sort(chunk);\n writeToTempFile(chunk);\n}\nmergeAllFiles();\n```\n\n**Approach 2: Replacement Selection**\n- Use heap of size k\n- Output minimum, replace with next input\n- If new element < just output, mark for next run\n- Produces runs up to 2k elements\n\n**Approach 3: Lossy Sampling**\n- If approximate sorting acceptable\n- Reservoir sampling for statistics\n- Bucket based on samples\n\n**Approach 4: Online Algorithms**\n- Min/max heap for median\n- Priority queue for top-K\n- Balanced BST for arbitrary queries\n\n**Key tradeoffs:**\n| Approach | Space | Accuracy | Latency |\n|----------|-------|----------|---------|\n| External sort | O(chunk) | Exact | High |\n| Sampling | O(samples) | Approximate | Low |\n| Data structures | O(k) | Exact for query | Low |\n\n---\n\n### Question 5: Compare TimSort and IntroSort - when would you choose each?\n\n**Answer:**\n\n| Aspect | TimSort | IntroSort |\n|--------|---------|-----------|\n| **Stability** | Stable | Unstable |\n| **Best case** | O(n) | O(n log n) |\n| **Worst case** | O(n log n) | O(n log n) |\n| **Space** | O(n) | O(log n) |\n| **Adaptive** | Yes (runs) | Limited (threshold) |\n\n**Choose TimSort when:**\n- Stability required (multi-key sorts)\n- Data likely has sorted runs\n- Objects with expensive comparison\n- Memory not constrained\n\n**Choose IntroSort when:**\n- Memory constrained (in-place)\n- Primitives (stability meaningless)\n- Random data expected\n- Maximum throughput needed\n\n**Real-world usage:**\n- Java `Arrays.sort(Object[])`: TimSort (stable)\n- Java `Arrays.sort(int[])`: Dual-Pivot QuickSort (unstable)\n- C++ `std::sort`: IntroSort (unstable)\n- C++ `std::stable_sort`: MergeSort variant (stable)\n- Python `sorted()`: TimSort (stable)\n\n---\n\n## 📋 Quick Reference\n\n### Algorithm Selection by Data Pattern\n\n| Data Pattern | Best Algorithm | Rationale |\n|--------------|----------------|-----------|\n| Random | QuickSort/IntroSort | Cache-efficient partitioning |\n| Nearly sorted | TimSort/Natural Merge | Exploits existing runs |\n| Many duplicates | 3-Way QuickSort | Partitions equals efficiently |\n| Small range integers | Counting Sort | O(n + k) |\n| Fixed-width keys | Radix Sort | O(d × n) |\n| Memory constrained | HeapSort | O(1) extra space |\n| Stability required | MergeSort/TimSort | Stable by design |\n| Parallel/SIMD | Bitonic Sort | Predictable access pattern |\n\n### Hybrid Sort Thresholds\n\n| Threshold | Typical Value | Purpose |\n|-----------|---------------|---------|\n| Insertion sort cutoff | 16-32 | QuickSort overhead |\n| IntroSort depth limit | 2·log₂(n) | Prevent O(n²) |\n| TimSort minRun | 32-64 | Merge efficiency |\n| Parallel sort minimum | 8192 | Fork/Join overhead |\n| Galloping threshold | 7 | Switch merge strategy |\n\n### Complexity Summary\n\n| Algorithm | Best | Average | Worst | Space | Stable |\n|-----------|------|---------|-------|-------|--------|\n| IntroSort | O(n log n) | O(n log n) | O(n log n) | O(log n) | No |\n| TimSort | O(n) | O(n log n) | O(n log n) | O(n) | Yes |\n| SmoothSort | O(n) | O(n log n) | O(n log n) | O(1) | No |\n| Block Sort | O(n log n) | O(n log n) | O(n log n) | O(1) | Yes |\n| Bitonic | O(n log² n) | O(n log² n) | O(n log² n) | O(1)* | No |\n| Patience | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes |\n\n*Bitonic sort is in-place but requires power-of-two padding\n\n---\n\n## 📅 Review Schedule\n\n| Day | Focus | Time |\n|-----|-------|------|\n| Day 1 | Read full article, understand IntroSort | 60 min |\n| Day 3 | Implement IntroSort from scratch | 30 min |\n| Day 7 | Implement Patience Sort, find LIS | 30 min |\n| Day 14 | Debug the broken IntroSort exercise | 15 min |\n| Day 30 | Compare performance of all algorithms | 20 min |\n\n---\n\n## 🔗 What's Next?\n\n**Part 8: Binary Search Mastery** covers:\n- Classic binary search and common bugs\n- Lower bound, upper bound, equal range\n- Binary search on answer (parametric search)\n- Rotated array variants\n- 2D matrix search\n\n**Key insight preview**: Binary search is more than finding an element - it's a technique for solving any problem where the answer space is monotonic.\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.099400Z","createdAt","2026-06-10T07:19:25.100380Z","updatedAt","2026-06-16T21:26:56.086200Z","readingTimeMinutes",30,"estimatedReadingTime","authorId",3,"authorUsername","tomasz_main","categoryName","Algorithms","readingTime","seriesId",2,"seriesOrder",7,"author",{"_31":55,"_103":57,"_104":105,"_106":107,"_108":-5,"_109":-5,"_110":-5,"_111":-5,"_112":-5},"category",{"_31":99,"_73":59,"_35":100,"_76":101,"_102":-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},135,"Timsort","timsort",145,"Patience Sort","patience-sort",144,"Introsort","introsort",146,"Block Sort","block-sort",147,"Adaptive","adaptive",6,"algorithms","Category for Algorithms","colorHex","username","firstName","Tomasz","lastName","Jarosz","profilePicture","bio","website","githubUrl","linkedinUrl"]