[{"_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",31,"title","Comparison-Based Sorting","slug","algorithms-part-4-comparison-based-sorting","excerpt","Deep dive into QuickSort, MergeSort, HeapSort, and TimSort with implementation details and practical trade-offs between these fundamental algorithms.","# Algorithms Compendium Part 4: Comparison-Based Sorting Deep Dive\n\nSorting is the most studied problem in computer science, and for good reason - it appears everywhere, from database indexing to rendering graphics. This article takes you deep into the four most important comparison-based sorting algorithms: QuickSort, MergeSort, HeapSort, and TimSort (Java's default).\n\nUnderstanding these algorithms at the implementation level transforms how you think about data processing and gives you the tools to make informed decisions in production systems.\n\n## 📋 At a Glance\n\n| Algorithm | Time (Avg) | Time (Worst) | Space | Stable | In-Place |\n|-----------|------------|--------------|-------|--------|----------|\n| QuickSort | O(n log n) | O(n²) | O(log n) | No | Yes |\n| MergeSort | O(n log n) | O(n log n) | O(n) | Yes | No |\n| HeapSort | O(n log n) | O(n log n) | O(1) | No | Yes |\n| TimSort | O(n log n) | O(n log n) | O(n) | Yes | No |\n\n---\n\n## 🎯 What You'll Learn\n\nAfter reading this article, you will be able to:\n\n- **Implement QuickSort** with multiple pivot strategies and 3-way partitioning\n- **Understand MergeSort's stability** and why it matters for complex objects\n- **Build HeapSort** from scratch using the heapify operation\n- **Explain TimSort's hybrid approach** and why Java chose it\n- **Prove the Ω(n log n) lower bound** for comparison-based sorting\n- **Choose the right algorithm** based on data characteristics\n\n---\n\n## 🔥 Production Story: The Sorted Data Disaster\n\nAn e-commerce platform had a product listing service that sorted items by price. Performance was excellent in testing with random data. In production, disaster struck.\n\n```java\n// ❌ The problematic code\npublic List sortByPrice(List products) {\n return products.stream()\n .sorted(Comparator.comparing(Product::getPrice))\n .collect(Collectors.toList());\n}\n```\n\n**What happened:**\n\nThe product database was already mostly sorted by price (products added in price tiers). When users filtered by category, results came back nearly sorted.\n\n```text\nTest data (random): 50,000 products sorted in 45ms\nProduction data (nearly sorted): 50,000 products sorted in 12 seconds\n```\n\n**The investigation revealed:**\n\nBefore Java 7, `Arrays.sort()` for objects used MergeSort. But for primitives, it used QuickSort with a fixed pivot strategy. A developer had converted Product prices to a primitive array for \"optimization\":\n\n```java\n// ❌ \"Optimized\" version that backfired\npublic List sortByPriceFast(List products) {\n double[] prices = products.stream()\n .mapToDouble(Product::getPrice)\n .toArray();\n\n // Primitive sort used QuickSort with first-element pivot\n Arrays.sort(prices); // O(n²) on sorted data!\n\n // ... reconstruct product list\n}\n```\n\nWith first-element pivot on sorted data, QuickSort degrades to O(n²).\n\n**The fix:**\n\n```java\n// ✅ Use object sort (TimSort) - handles sorted data well\npublic List sortByPrice(List products) {\n List result = new ArrayList<>(products);\n result.sort(Comparator.comparing(Product::getPrice));\n return result;\n}\n```\n\n**Result:** TimSort recognized the nearly-sorted pattern and completed in 15ms.\n\n**The lesson:** Algorithm choice matters. QuickSort's O(n²) worst case isn't theoretical - it happens with real data patterns. Know your data.\n\n---\n\n## 🧠 Mental Model: The Sorting Spectrum\n\nThink of sorting algorithms on a spectrum of trade-offs:\n\n```text\n┌─────────────────────────────────────────────────────────────────────┐\n│ SORTING ALGORITHM SPECTRUM │\n├─────────────────────────────────────────────────────────────────────┤\n│ │\n│ SPEED (average case) │\n│ ════════════════════ │\n│ QuickSort ←──────────────── Best average case │\n│ TimSort ←──────────────── Adaptive to patterns │\n│ MergeSort ←──────────────── Consistent │\n│ HeapSort ←──────────────── Slightly slower │\n│ │\n│ WORST CASE GUARANTEE │\n│ ════════════════════ │\n│ MergeSort ←──────────────── Always O(n log n) │\n│ HeapSort ←──────────────── Always O(n log n) │\n│ TimSort ←──────────────── Always O(n log n) │\n│ QuickSort ←──────────────── O(n²) possible │\n│ │\n│ MEMORY USAGE │\n│ ════════════════════ │\n│ HeapSort ←──────────────── O(1) extra │\n│ QuickSort ←──────────────── O(log n) stack │\n│ MergeSort ←──────────────── O(n) extra │\n│ TimSort ←──────────────── O(n) extra │\n│ │\n│ STABILITY │\n│ ════════════════════ │\n│ MergeSort ←──────────────── Stable │\n│ TimSort ←──────────────── Stable │\n│ QuickSort ←──────────────── Unstable │\n│ HeapSort ←──────────────── Unstable │\n│ │\n└─────────────────────────────────────────────────────────────────────┘\n```\n\n**Stability matters when:**\n- Sorting objects by multiple fields\n- Preserving previous sort order\n- User expectations (stable sorts feel \"less random\")\n\n### 🎮 Try It Yourself\n\nCompare all sorting algorithms interactively. Use the dropdown to switch between algorithms and observe how each one approaches the problem differently:\n\n```visualizer-sorting\nalgorithm: quick\nsize: 20\n```\n\n---\n\n## 🔬 Deep Dive\n\n### 1. QuickSort: The Speed Champion\n\nQuickSort is often the fastest in practice due to excellent cache locality and low constant factors.\n\n**Interactive Visualization:** See QuickSort in action - watch how the pivot partitions the array:\n\n```visualizer-sorting\nalgorithm: quick\nsize: 15\n```\n\n```java\n// ✅ QuickSort with random pivot and optimizations\npublic class QuickSort {\n\n private static final int INSERTION_THRESHOLD = 16;\n private static final Random random = new Random();\n\n public static void sort(int[] arr) {\n quickSort(arr, 0, arr.length - 1);\n }\n\n private static void quickSort(int[] arr, int low, int high) {\n // Optimization: use insertion sort for small subarrays\n if (high - low < INSERTION_THRESHOLD) {\n insertionSort(arr, low, high);\n return;\n }\n\n // Random pivot to avoid O(n²) on sorted data\n int pivotIndex = partition(arr, low, high);\n\n quickSort(arr, low, pivotIndex - 1);\n quickSort(arr, pivotIndex + 1, high);\n }\n\n private static int partition(int[] arr, int low, int high) {\n // Random pivot selection\n int randomIndex = low + random.nextInt(high - low + 1);\n swap(arr, randomIndex, high);\n\n int pivot = arr[high];\n int i = low - 1;\n\n for (int j = low; j < high; j++) {\n if (arr[j] <= pivot) {\n i++;\n swap(arr, i, j);\n }\n }\n\n swap(arr, i + 1, high);\n return i + 1;\n }\n\n private static void insertionSort(int[] arr, int low, int high) {\n for (int i = low + 1; i <= high; i++) {\n int key = arr[i];\n int j = i - 1;\n while (j >= low && 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 temp = arr[i];\n arr[i] = arr[j];\n arr[j] = temp;\n }\n}\n```\n\n**3-Way Partitioning (Dutch National Flag):**\n\nWhen there are many duplicates, standard QuickSort degrades. 3-way partitioning handles this:\n\n```java\n// ✅ 3-way partitioning for arrays with duplicates\nprivate static void quickSort3Way(int[] arr, int low, int high) {\n if (low >= high) return;\n\n int lt = low; // arr[low..lt-1] < pivot\n int gt = high; // arr[gt+1..high] > pivot\n int i = low + 1; // arr[lt..i-1] == pivot\n int pivot = arr[low];\n\n while (i <= gt) {\n if (arr[i] < pivot) {\n swap(arr, lt++, i++);\n } else if (arr[i] > pivot) {\n swap(arr, i, gt--);\n } else {\n i++;\n }\n }\n\n // Now: arr[low..lt-1] < pivot = arr[lt..gt] < arr[gt+1..high]\n quickSort3Way(arr, low, lt - 1);\n quickSort3Way(arr, gt + 1, high);\n}\n```\n\n**Why QuickSort is fast:**\n\n1. **Cache locality**: Works on contiguous memory\n2. **In-place**: No extra array allocation\n3. **Few swaps**: Only swaps when necessary\n4. **Branch prediction**: Comparison loop is predictable\n\n### 2. MergeSort: The Stable Workhorse\n\nMergeSort guarantees O(n log n) and stability, making it ideal for objects.\n\n**Interactive Visualization:** Watch MergeSort divide and conquer:\n\n```visualizer-sorting\nalgorithm: merge\nsize: 15\n```\n\n```java\n// ✅ MergeSort with optimizations\npublic class MergeSort {\n\n private static final int INSERTION_THRESHOLD = 16;\n\n public static > void sort(T[] arr) {\n @SuppressWarnings(\"unchecked\")\n T[] temp = (T[]) new Comparable[arr.length];\n mergeSort(arr, temp, 0, arr.length - 1);\n }\n\n private static > void mergeSort(\n T[] arr, T[] temp, int low, int high) {\n\n // Use insertion sort for small arrays\n if (high - low < INSERTION_THRESHOLD) {\n insertionSort(arr, low, high);\n return;\n }\n\n int mid = low + (high - low) / 2;\n\n mergeSort(arr, temp, low, mid);\n mergeSort(arr, temp, mid + 1, high);\n\n // Optimization: skip merge if already sorted\n if (arr[mid].compareTo(arr[mid + 1]) <= 0) {\n return;\n }\n\n merge(arr, temp, low, mid, high);\n }\n\n private static > void merge(\n T[] arr, T[] temp, int low, int mid, int high) {\n\n // Copy to temp\n System.arraycopy(arr, low, temp, low, high - low + 1);\n\n int i = low, j = mid + 1, k = low;\n\n while (i <= mid && j <= high) {\n // <= for stability (prefer left element when equal)\n if (temp[i].compareTo(temp[j]) <= 0) {\n arr[k++] = temp[i++];\n } else {\n arr[k++] = temp[j++];\n }\n }\n\n // Copy remaining left elements\n while (i <= mid) {\n arr[k++] = temp[i++];\n }\n // Right elements already in place\n }\n\n private static > void insertionSort(\n T[] arr, int low, int high) {\n for (int i = low + 1; i <= high; i++) {\n T key = arr[i];\n int j = i - 1;\n while (j >= low && arr[j].compareTo(key) > 0) {\n arr[j + 1] = arr[j];\n j--;\n }\n arr[j + 1] = key;\n }\n }\n}\n```\n\n**Why stability matters:**\n\n```java\n// Sorting employees by department, then by salary\nList employees = getEmployees();\n\n// First sort by salary\nemployees.sort(Comparator.comparing(Employee::getSalary));\n\n// Then sort by department (stable sort preserves salary order within dept)\nemployees.sort(Comparator.comparing(Employee::getDepartment));\n\n// Result: Grouped by department, ordered by salary within each department\n// This ONLY works with stable sort!\n```\n\n### 3. HeapSort: The Memory Champion\n\nHeapSort achieves O(n log n) worst case with O(1) extra space.\n\n```java\n// ✅ HeapSort implementation\npublic class HeapSort {\n\n public static void sort(int[] arr) {\n int n = arr.length;\n\n // Build max heap (heapify from bottom up)\n for (int i = n / 2 - 1; i >= 0; i--) {\n heapify(arr, n, i);\n }\n\n // Extract elements one by one\n for (int i = n - 1; i > 0; i--) {\n // Move current root (max) to end\n swap(arr, 0, i);\n\n // Heapify reduced heap\n heapify(arr, i, 0);\n }\n }\n\n private static void heapify(int[] arr, int heapSize, int rootIndex) {\n int largest = rootIndex;\n int left = 2 * rootIndex + 1;\n int right = 2 * rootIndex + 2;\n\n if (left < heapSize && arr[left] > arr[largest]) {\n largest = left;\n }\n\n if (right < heapSize && arr[right] > arr[largest]) {\n largest = right;\n }\n\n if (largest != rootIndex) {\n swap(arr, rootIndex, largest);\n heapify(arr, heapSize, largest);\n }\n }\n\n private static void swap(int[] arr, int i, int j) {\n int temp = arr[i];\n arr[i] = arr[j];\n arr[j] = temp;\n }\n}\n```\n\n**Heap visualization:**\n\n```text\nArray: [16, 14, 10, 8, 7, 9, 3, 2, 4, 1]\n\nAs binary heap:\n 16\n / \\\n 14 10\n / \\ / \\\n 8 7 9 3\n / \\ /\n 2 4 1\n\nParent of i: (i-1)/2\nLeft child: 2*i + 1\nRight child: 2*i + 2\n```\n\n**Why HeapSort isn't the default:**\n\n1. Poor cache locality (jumps around the array)\n2. More comparisons than QuickSort\n3. Not stable\n4. But: guaranteed O(n log n) and O(1) space\n\n### 4. TimSort: Java's Default\n\nTimSort is a hybrid algorithm combining MergeSort and InsertionSort, optimized for real-world data.\n\n```java\n// ✅ Simplified TimSort implementation\npublic class TimSort {\n\n private static final int MIN_MERGE = 32;\n\n public static void sort(int[] arr) {\n int n = arr.length;\n\n // Step 1: Sort small runs using insertion sort\n for (int i = 0; i < n; i += MIN_MERGE) {\n insertionSort(arr, i, Math.min(i + MIN_MERGE - 1, n - 1));\n }\n\n // Step 2: Merge runs, doubling size each iteration\n for (int size = MIN_MERGE; size < n; size *= 2) {\n for (int left = 0; left < n; left += 2 * size) {\n int mid = left + size - 1;\n int right = Math.min(left + 2 * size - 1, n - 1);\n\n if (mid < right) {\n merge(arr, left, mid, right);\n }\n }\n }\n }\n\n // The real TimSort also:\n // - Detects and exploits existing runs (ascending or descending)\n // - Uses galloping mode for highly unbalanced merges\n // - Maintains invariants to balance merge sizes\n}\n```\n\n**What makes TimSort special:**\n\n1. **Exploits existing order**: Finds natural runs in data\n2. **Adaptive**: Nearly-sorted data is O(n)\n3. **Stable**: Critical for object sorting\n4. **Galloping mode**: Optimizes unbalanced merges\n\n**Real TimSort run detection:**\n\n```java\n// TimSort looks for natural runs\n// Input: [1, 2, 5, 8, 3, 4, 6, 7, 9]\n// └──────┘ └────────────┘\n// run 1 run 2\n\n// If descending run found, reverse it:\n// Input: [8, 5, 2, 1, ...]\n// After: [1, 2, 5, 8, ...] (reversed in-place)\n```\n\n### 5. The Comparison Lower Bound: Ω(n log n)\n\nWhy can't we sort faster than O(n log n) using comparisons?\n\n**Proof using decision trees:**\n\n```text\nSorting n elements means finding the correct permutation\namong n! possible permutations.\n\nAny comparison-based algorithm is a decision tree:\n- Each internal node is a comparison (a < b?)\n- Each leaf is a permutation (sorted order)\n\nA binary tree with L leaves has height ≥ log₂(L)\n\nWe need n! leaves (one per permutation)\nHeight ≥ log₂(n!)\n\nUsing Stirling's approximation:\nlog₂(n!) ≈ n log₂(n) - n log₂(e) + O(log n)\n ≈ n log₂(n)\n\nTherefore: Minimum comparisons = Ω(n log n)\n```\n\n**This means:**\n- No comparison-based sort can beat O(n log n)\n- QuickSort, MergeSort, HeapSort are asymptotically optimal\n- To go faster, we need non-comparison sorts (Part 5)\n\n---\n\n## ⚠️ Common Mistakes\n\n### Mistake 1: QuickSort with Bad Pivot on Sorted Data\n\n```java\n// ❌ Always choosing first element as pivot\nprivate static int partition(int[] arr, int low, int high) {\n int pivot = arr[low]; // BAD on sorted data!\n // ...\n}\n\n// On sorted array [1, 2, 3, 4, 5]:\n// Pivot = 1, partition creates [1] and [2,3,4,5]\n// Pivot = 2, partition creates [2] and [3,4,5]\n// ...\n// n iterations, each O(n) work = O(n²)\n\n// ✅ Random pivot\nint pivotIndex = low + random.nextInt(high - low + 1);\n\n// ✅ Median of three\nint mid = low + (high - low) / 2;\nint pivotIndex = medianOfThree(arr, low, mid, high);\n```\n\n### Mistake 2: Unstable Sort for Objects\n\n```java\n// ❌ Using HeapSort/QuickSort when stability needed\nList transactions = getTransactions();\n\n// First sort by amount\ntransactions.sort(Comparator.comparing(Transaction::getAmount));\n\n// Then sort by date using unstable sort\nheapSort(transactions, Comparator.comparing(Transaction::getDate));\n\n// Result: Transactions on same date may not be ordered by amount!\n\n// ✅ Use stable sort (MergeSort/TimSort)\ntransactions.sort(Comparator.comparing(Transaction::getDate)\n .thenComparing(Transaction::getAmount));\n```\n\n### Mistake 3: Not Using Insertion Sort for Small Arrays\n\n```java\n// ❌ Recursing all the way to size 1\nprivate static void quickSort(int[] arr, int low, int high) {\n if (low >= high) return; // Base case at size 1\n // ... lots of overhead for tiny arrays\n}\n\n// ✅ Switch to insertion sort for small arrays\nprivate static void quickSort(int[] arr, int low, int high) {\n if (high - low < 16) {\n insertionSort(arr, low, high); // Less overhead\n return;\n }\n // ...\n}\n```\n\n---\n\n## 🐛 Debug This\n\nThe following QuickSort has a subtle bug. Find it:\n\n```java\npublic class BuggyQuickSort {\n\n public static void sort(int[] arr) {\n quickSort(arr, 0, arr.length - 1);\n }\n\n private static void quickSort(int[] arr, int low, int high) {\n if (low >= high) return;\n\n int pivotIndex = partition(arr, low, high);\n\n quickSort(arr, low, pivotIndex); // Sort left part\n quickSort(arr, pivotIndex + 1, high); // Sort right part\n }\n\n private static int partition(int[] arr, int low, int high) {\n int pivot = arr[high];\n int i = low - 1;\n\n for (int j = low; j < high; j++) {\n if (arr[j] <= pivot) {\n i++;\n swap(arr, i, j);\n }\n }\n\n swap(arr, i + 1, high);\n return i + 1;\n }\n\n private static void swap(int[] arr, int i, int j) {\n int temp = arr[i];\n arr[i] = arr[j];\n arr[j] = temp;\n }\n}\n\n// Test: [3, 1, 2]\n// Sometimes works, sometimes StackOverflowError!\n```\n\n

Click to reveal the bug and solution

\n\n**The Bug:**\n\nThe recursive call `quickSort(arr, low, pivotIndex)` should be `quickSort(arr, low, pivotIndex - 1)`.\n\nWith `pivotIndex` included in the left partition, when pivot ends up at `high`, we recursively call:\n- `quickSort(arr, low, high)` - the same range!\n\n**Trace for [2, 1]:**\n```text\nquickSort(arr, 0, 1)\n partition returns pivotIndex = 1\n quickSort(arr, 0, 1) ← Same call! Infinite recursion\n partition returns pivotIndex = 1\n quickSort(arr, 0, 1) ← Stack overflow!\n```\n\n**The Fix:**\n\n```java\nprivate static void quickSort(int[] arr, int low, int high) {\n if (low >= high) return;\n\n int pivotIndex = partition(arr, low, high);\n\n quickSort(arr, low, pivotIndex - 1); // ✅ Exclude pivot\n quickSort(arr, pivotIndex + 1, high);\n}\n```\n\nThe pivot is already in its final position after partition, so we exclude it from both recursive calls.\n\n

\n\n---\n\n## 💻 Exercises\n\n### Exercise 1: Implement Median-of-Three Pivot ⭐\n\nImplement median-of-three pivot selection for QuickSort:\n\n```java\n// Select pivot as median of first, middle, and last elements\nprivate static int medianOfThree(int[] arr, int low, int high) {\n // Your code here\n // Return the INDEX of the median element\n}\n```\n\n

Solution

\n\n```java\nprivate static int medianOfThree(int[] arr, int low, int high) {\n int mid = low + (high - low) / 2;\n\n // Sort low, mid, high positions\n if (arr[low] > arr[mid]) swap(arr, low, mid);\n if (arr[low] > arr[high]) swap(arr, low, high);\n if (arr[mid] > arr[high]) swap(arr, mid, high);\n\n // Now arr[low] <= arr[mid] <= arr[high]\n // Return mid as pivot index\n return mid;\n}\n\n// Usage in partition:\nprivate static int partition(int[] arr, int low, int high) {\n int pivotIndex = medianOfThree(arr, low, high);\n swap(arr, pivotIndex, high); // Move pivot to end\n // ... rest of partition\n}\n```\n\nMedian-of-three avoids worst case on sorted data while being cheaper than random.\n

\n\n---\n\n### Exercise 2: Count Comparisons ⭐⭐\n\nModify MergeSort to count the number of comparisons:\n\n```java\npublic static long mergeSortWithCount(int[] arr) {\n // Return total number of comparisons made\n}\n```\n\n

Solution

\n\n```java\npublic static long mergeSortWithCount(int[] arr) {\n int[] temp = new int[arr.length];\n return mergeSort(arr, temp, 0, arr.length - 1);\n}\n\nprivate static long mergeSort(int[] arr, int[] temp, int low, int high) {\n if (low >= high) return 0;\n\n long comparisons = 0;\n int mid = low + (high - low) / 2;\n\n comparisons += mergeSort(arr, temp, low, mid);\n comparisons += mergeSort(arr, temp, mid + 1, high);\n comparisons += merge(arr, temp, low, mid, high);\n\n return comparisons;\n}\n\nprivate static long merge(int[] arr, int[] temp, int low, int mid, int high) {\n System.arraycopy(arr, low, temp, low, high - low + 1);\n\n int i = low, j = mid + 1, k = low;\n long comparisons = 0;\n\n while (i <= mid && j <= high) {\n comparisons++; // Count each comparison\n if (temp[i] <= temp[j]) {\n arr[k++] = temp[i++];\n } else {\n arr[k++] = temp[j++];\n }\n }\n\n while (i <= mid) arr[k++] = temp[i++];\n\n return comparisons;\n}\n\n// For n elements, expect approximately n*log2(n) - n + 1 comparisons\n```\n

\n\n---\n\n### Exercise 3: In-Place MergeSort ⭐⭐⭐\n\nImplement MergeSort using O(1) extra space (in-place merge):\n\n```java\n// Hint: Use rotation-based merge\npublic static void inPlaceMergeSort(int[] arr) {\n // Your code here\n}\n```\n\n

Solution

\n\n```java\npublic static void inPlaceMergeSort(int[] arr) {\n inPlaceMergeSort(arr, 0, arr.length - 1);\n}\n\nprivate static void inPlaceMergeSort(int[] arr, int low, int high) {\n if (low >= high) return;\n\n int mid = low + (high - low) / 2;\n inPlaceMergeSort(arr, low, mid);\n inPlaceMergeSort(arr, mid + 1, high);\n inPlaceMerge(arr, low, mid, high);\n}\n\nprivate static void inPlaceMerge(int[] arr, int low, int mid, int high) {\n int i = low, j = mid + 1;\n\n while (i <= mid && j <= high) {\n if (arr[i] <= arr[j]) {\n i++;\n } else {\n // arr[j] needs to go to position i\n // Rotate arr[i..j] left by 1\n int temp = arr[j];\n for (int k = j; k > i; k--) {\n arr[k] = arr[k - 1];\n }\n arr[i] = temp;\n\n i++;\n mid++;\n j++;\n }\n }\n}\n\n// Note: This is O(n² log n) due to rotation overhead\n// True O(n log n) in-place merge is complex (see block merge sort)\n```\n

\n\n---\n\n### Exercise 4: Iterative QuickSort ⭐⭐⭐\n\nImplement QuickSort without recursion (using explicit stack):\n\n```java\npublic static void iterativeQuickSort(int[] arr) {\n // Your code here\n}\n```\n\n

Solution

\n\n```java\npublic static void iterativeQuickSort(int[] arr) {\n Deque stack = new ArrayDeque<>();\n stack.push(new int[]{0, arr.length - 1});\n\n while (!stack.isEmpty()) {\n int[] range = stack.pop();\n int low = range[0], high = range[1];\n\n if (low >= high) continue;\n\n int pivotIndex = partition(arr, low, high);\n\n // Push larger partition first (limits stack depth to O(log n))\n if (pivotIndex - low > high - pivotIndex) {\n stack.push(new int[]{low, pivotIndex - 1});\n stack.push(new int[]{pivotIndex + 1, high});\n } else {\n stack.push(new int[]{pivotIndex + 1, high});\n stack.push(new int[]{low, pivotIndex - 1});\n }\n }\n}\n\nprivate static int partition(int[] arr, int low, int high) {\n int pivotIndex = low + new Random().nextInt(high - low + 1);\n swap(arr, pivotIndex, high);\n\n int pivot = arr[high];\n int i = low - 1;\n\n for (int j = low; j < high; j++) {\n if (arr[j] <= pivot) {\n swap(arr, ++i, j);\n }\n }\n swap(arr, i + 1, high);\n return i + 1;\n}\n```\n\nBy always processing the smaller partition first and pushing the larger, we guarantee O(log n) stack space.\n

\n\n---\n\n### Exercise 5: Detect Natural Runs (TimSort Style) ⭐⭐⭐⭐\n\nImplement run detection like TimSort:\n\n```java\n// Find natural ascending or descending runs\n// Return array of run start indices and their lengths\npublic static List findRuns(int[] arr) {\n // Each int[] is {startIndex, length, ascending?}\n // Your code here\n}\n```\n\n

Solution

\n\n```java\npublic static List findRuns(int[] arr) {\n List runs = new ArrayList<>();\n int n = arr.length;\n if (n == 0) return runs;\n\n int runStart = 0;\n\n while (runStart < n) {\n int runEnd = runStart;\n boolean ascending;\n\n if (runEnd + 1 < n) {\n if (arr[runEnd] <= arr[runEnd + 1]) {\n // Ascending run\n ascending = true;\n while (runEnd + 1 < n && arr[runEnd] <= arr[runEnd + 1]) {\n runEnd++;\n }\n } else {\n // Descending run\n ascending = false;\n while (runEnd + 1 < n && arr[runEnd] > arr[runEnd + 1]) {\n runEnd++;\n }\n }\n } else {\n ascending = true; // Single element\n }\n\n int length = runEnd - runStart + 1;\n runs.add(new int[]{runStart, length, ascending ? 1 : 0});\n\n runStart = runEnd + 1;\n }\n\n return runs;\n}\n\n// Example: [5, 3, 1, 2, 4, 6, 8, 7, 5]\n// Runs: [(0, 3, desc), (3, 4, asc), (7, 2, desc)]\n// TimSort would reverse descending runs to make them ascending\n```\n

\n\n---\n\n## 🎤 Interview Questions\n\n### Question #1: When would you choose HeapSort over QuickSort?\n\n**What interviewers want to hear**: Understanding of trade-offs and real constraints.\n\n**Strong answer**:\nChoose HeapSort when:\n\n1. **Strict memory constraints**: HeapSort uses O(1) extra space vs O(log n) for QuickSort's stack\n\n2. **Worst-case guarantee required**: HeapSort is always O(n log n), QuickSort can degrade to O(n²)\n\n3. **Embedded systems**: Predictable performance matters more than average speed\n\n4. **Partial sorting**: To find top-k elements, build heap in O(n), extract k in O(k log n)\n\nHowever, QuickSort is usually preferred because:\n- Better cache locality (sequential access pattern)\n- Lower constant factors\n- In practice, O(n²) is avoidable with good pivot selection\n\n---\n\n### Question #2: Explain why MergeSort is stable but QuickSort is not.\n\n**What interviewers want to hear**: Deep understanding of algorithm mechanics.\n\n**Strong answer**:\n**Stability definition**: Equal elements maintain their relative order.\n\n**MergeSort is stable because:**\nDuring merge, when elements are equal, we always take from the left subarray first:\n\n```java\nif (left[i] <= right[j]) { // <= not <\n result[k++] = left[i++];\n}\n```\n\nEqual elements from the left half (which came earlier in the original array) are placed first.\n\n**QuickSort is unstable because:**\nDuring partition, elements are swapped based on comparison with pivot. The relative order of equal elements is not preserved:\n\n```java\n// Original: [3a, 1, 3b, 2] (3a appears before 3b)\n// After partition with pivot=2: [1, 2, 3b, 3a] (order reversed!)\n```\n\nElements equal to the pivot can end up in either partition depending on their position.\n\n---\n\n### Question #3: Why does Java use different sorting algorithms for primitives vs objects?\n\n**What interviewers want to hear**: Knowledge of Java internals and practical trade-offs.\n\n**Strong answer**:\n**Before Java 7:**\n- Primitives: QuickSort (faster, no stability needed)\n- Objects: MergeSort (stable, needed for Comparable contract)\n\n**After Java 7:**\n- Primitives: Dual-Pivot QuickSort (even faster)\n- Objects: TimSort (stable, adaptive)\n\n**Reasons:**\n\n1. **Stability requirement**: Objects sorted by Comparator should maintain relative order for equals. MergeSort/TimSort guarantee this.\n\n2. **Comparison cost**: Object comparison (calling compareTo()) is expensive. TimSort minimizes comparisons through runs.\n\n3. **Primitive comparison is cheap**: QuickSort's fewer swaps and better cache performance win for primitives.\n\n4. **Real-world data patterns**: TimSort exploits partially sorted data common in objects (timestamps, IDs).\n\n---\n\n### Question #4: How would you sort a nearly-sorted array efficiently?\n\n**What interviewers want to hear**: Adaptive algorithms knowledge.\n\n**Strong answer**:\nFor nearly-sorted data:\n\n**Best options:**\n\n1. **Insertion Sort**: O(n) for nearly sorted because elements are close to their final position\n\n2. **TimSort**: Detects natural runs, nearly-sorted input is O(n)\n\n3. **Adaptive ShellSort**: Exploits partial order\n\n**Why these work:**\n- Insertion sort moves elements short distances efficiently\n- TimSort identifies long runs and minimizes merge work\n- Already-sorted subsequences are preserved\n\n**Avoid:**\n- HeapSort: Always O(n log n), doesn't exploit order\n- Standard QuickSort: Sorted data can trigger O(n²)\n\n```java\n// Check if nearly sorted, choose algorithm\nif (isNearlySorted(arr)) {\n insertionSort(arr); // O(n)\n} else {\n quickSort(arr); // O(n log n)\n}\n```\n\n---\n\n### Question #5: Prove that any comparison-based sort requires Ω(n log n) comparisons.\n\n**What interviewers want to hear**: Theoretical understanding with clear reasoning.\n\n**Strong answer**:\n**Proof outline:**\n\n1. Sorting n distinct elements means determining which of n! permutations is correct\n\n2. Each comparison answers a yes/no question, eliminating at most half of remaining permutations\n\n3. A comparison-based sort is a decision tree where:\n - Internal nodes are comparisons\n - Leaves are permutations (sorted outputs)\n - Tree must have at least n! leaves\n\n4. A binary tree with L leaves has height at least log₂(L)\n\n5. Therefore: height ≥ log₂(n!)\n\n6. Using Stirling's approximation:\n ```\n log₂(n!) ≈ log₂((n/e)^n × √(2πn))\n = n log₂(n) - n log₂(e) + O(log n)\n ≈ n log₂(n)\n ```\n\n7. **Conclusion**: Any comparison sort needs at least Ω(n log n) comparisons\n\nThis is a lower bound - no comparison-based algorithm can beat it. Non-comparison sorts (counting, radix) bypass this by not using comparisons.\n\n---\n\n## 📋 Quick Reference\n\n### Algorithm Selection Guide\n\n```text\nNeed to sort?\n│\n├── Primitives?\n│ └── Use Arrays.sort() (Dual-Pivot QuickSort)\n│\n├── Objects?\n│ ├── Need stability? ────────→ Arrays.sort() / Collections.sort() (TimSort)\n│ └── Don't need stability?\n│ ├── Memory constrained? → HeapSort\n│ └── Otherwise ──────────→ TimSort (still best)\n│\n├── Nearly sorted data?\n│ └── TimSort or Insertion Sort\n│\n├── Many duplicates?\n│ └── 3-Way QuickSort\n│\n├── External/disk sort?\n│ └── MergeSort (sequential access pattern)\n│\n└── Embedded/real-time?\n └── HeapSort (guaranteed O(n log n))\n```\n\n### Complexity Summary\n\n| Sort | Best | Average | Worst | Space | Stable |\n|------|------|---------|-------|-------|--------|\n| QuickSort | O(n log n) | O(n log n) | O(n²) | O(log n) | No |\n| MergeSort | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes |\n| HeapSort | O(n log n) | O(n log n) | O(n log n) | O(1) | No |\n| TimSort | O(n) | O(n log n) | O(n log n) | O(n) | Yes |\n| Insertion | O(n) | O(n²) | O(n²) | O(1) | Yes |\n\n### Java Sorting Methods\n\n```java\n// Primitives - Dual-Pivot QuickSort\nArrays.sort(int[] arr);\nArrays.sort(int[] arr, int fromIndex, int toIndex);\n\n// Objects - TimSort\nArrays.sort(T[] arr);\nArrays.sort(T[] arr, Comparator c);\nCollections.sort(List list);\nlist.sort(Comparator c);\n\n// Parallel sort (for large arrays)\nArrays.parallelSort(int[] arr);\nArrays.parallelSort(T[] arr);\n```\n\n---\n\n## 📝 Summary & Key Takeaways\n\n### Core Principles\n\n1. **QuickSort is fastest on average** but has O(n²) worst case - use random pivot\n2. **MergeSort guarantees O(n log n)** and stability - essential for objects\n3. **HeapSort uses O(1) space** but has poor cache locality\n4. **TimSort adapts to data patterns** - Java's smart default choice\n5. **Ω(n log n) is the lower bound** for comparison-based sorting\n\n### What You Can Do Now\n\n- Implement all four algorithms from scratch\n- Choose the right algorithm based on requirements\n- Explain why Java uses different sorts for primitives vs objects\n- Prove the comparison sort lower bound\n- Optimize QuickSort with pivot strategies and 3-way partitioning\n\n---\n\n## 📅 Review Schedule\n\n| Day | Task | Time |\n|-----|------|------|\n| Day 1 | Review complexity table | 5 min |\n| Day 3 | Implement QuickSort with random pivot | 15 min |\n| Day 7 | Implement HeapSort from memory | 15 min |\n| Day 14 | Redo Debug This exercise | 10 min |\n| Day 30 | Explain all four algorithms aloud | 15 min |\n\n---\n\n*Next in series: [Part 5: Linear Time Sorting - Counting Sort, Radix Sort & Bucket Sort]*\n","featuredImage","isPublished","isFeatured","subscriptionType","BASIC","publishedAt","2026-06-10T07:19:25.052662Z","createdAt","2026-06-10T07:19:25.053446Z","updatedAt","2026-06-16T21:26:56.086200Z","readingTimeMinutes",21,"estimatedReadingTime","authorId",3,"authorUsername","tomasz_main","categoryName","Algorithms","readingTime","seriesId",2,"seriesOrder",4,"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",133,"Sorting","sorting",131,"Quicksort","quicksort",132,"Mergesort","mergesort",134,"Heapsort","heapsort",6,"algorithms","Category for Algorithms","colorHex","username","firstName","Tomasz","lastName","Jarosz","profilePicture","bio","website","githubUrl","linkedinUrl"]