{"title":"Multi-threaded Quick Sort","description":"","content":"# Multi-threaded Quick Sort\n\nYou need to sort 100 million integers. Your machine has 8 CPU cores. Sequential quick sort takes 6 seconds. Can you make it 8x faster?\n\nThe short answer: probably not 8x, but you can get meaningful speedup. Quick sort, like merge sort, has a divide-and-conquer structure that seems perfect for parallelization. Split the array around a pivot, sort both sides in parallel, done. But there's a catch: the partition step that splits the array is inherently sequential in its basic form. This makes quick sort trickier to parallelize effectively than merge sort.\n\nQuick sort is the workhorse of production systems. C's `qsort`, .NET's `Array.Sort`, and many database query engines use quick sort or its variants. Understanding how to parallelize it teaches you about handling unbalanced workloads, pivot selection, and why some algorithms resist parallelization more than others.\n\nIn this chapter, we'll build multi-threaded quick sort from scratch, explore three approaches from naive to production-ready, examine parallel partition strategies, and compare with parallel merge sort.\n\n---\n\n## Problem Statement\n\n### Sequential Quick Sort Recap\n\nQuick sort follows a different divide-and-conquer pattern than merge sort. Instead of dividing equally and doing work during the merge, quick sort does work during the divide (partition) and combines trivially:\n\n1. Choose a pivot element\n2. Partition the array so elements less than pivot are on the left, greater on the right\n3. Recursively sort left and right partitions\n4. No merge needed, the array is already sorted in place\n\nThe recurrence relation is:\n\n\n```shell\nT(n) = T(k) + T(n-k-1) + O(n)\n```\n\n\nWhere k is the number of elements less than the pivot. The O(n) term comes from the partition step, which must examine every element.\n\nIn the average case (pivot splits evenly), this gives O(n log n). In the worst case (pivot is always min or max), we get O(n²).\n\n\n```mermaid\nflowchart TB\n subgraph PartitionPhase[\"Partition Phase (O(n) work)\"]\n A[\"[38, 27, 43, 3, 9, 82, 10]\"]:::primary\n P[\"Pivot = 27\"]:::orange\n B[\"[3, 9, 10] | 27 | [38, 43, 82]\"]:::secondary\n end\n\n A --> P --> B\n\n subgraph RecursiveSort[\"Recursive Sort\"]\n L[\"[3, 9, 10]\"]:::green\n R[\"[38, 43, 82]\"]:::green\n LS[\"[3, 9, 10] sorted\"]:::teal\n RS[\"[38, 43, 82] sorted\"]:::teal\n end\n\n B --> L\n B --> R\n L --> LS\n R --> RS\n\n subgraph Result[\"Result (no merge needed)\"]\n FINAL[\"[3, 9, 10, 27, 38, 43, 82]\"]:::purple\n end\n\n LS --> FINAL\n RS --> FINAL\n\n classDef primary fill:#00ceff,stroke:#000,color:#000\n classDef secondary fill:#38d9a9,stroke:#000,color:#000\n classDef orange fill:#ffa94d,stroke:#000,color:#000\n classDef green fill:#69db7c,stroke:#000,color:#000\n classDef teal fill:#3bc9db,stroke:#000,color:#000\n classDef purple fill:#9775fa,stroke:#000,color:#000\n```\n\n\nThe key difference from merge sort: quick sort does O(n) work at the start of each recursive call (partition), not at the end (merge). This changes the parallelization strategy.\n\n### The Parallelization Goal\n\nLike merge sort, the left and right recursive calls are independent. They can run in parallel. But unlike merge sort, we have two challenges:\n\n1. **Uneven splits:** Bad pivot selection creates unbalanced workloads\n2. **Sequential partition:** The partition step is O(n) and harder to parallelize than merge\n\n**Performance Metrics:**\n\n\n| Metric | Sequential | Parallel (sequential partition) | Parallel (parallel partition) |\n|--------|------------|--------------------------------|-------------------------------|\n| Work | O(n log n) avg | O(n log n) avg | O(n log n) avg |\n| Span | O(n log n) avg | O(n) avg | O(log² n) avg |\n| Parallelism | 1 | O(log n) | O(n / log n) |\n\n\nThe span with sequential partition is O(n) because the partition at the top level takes O(n) time regardless of how many cores we have.\n\n### API Design\n\n\n```java\n// Sort array using all available cores\nvoid parallelQuickSort(int[] arr)\n\n// Sort array using specified number of threads\nvoid parallelQuickSort(int[] arr, int numThreads)\n```\n\n\n### Interview Context\n\nInterviewers ask about parallel quick sort to test:\n\n1. **Understanding partition as bottleneck:** Unlike merge sort where merge is the bottleneck\n2. **Load balancing awareness:** How bad pivots affect parallel performance\n3. **Work-span analysis:** How partition affects the critical path\n4. **Advanced techniques:** Block partition, three-way partition for duplicates\n\n:::info Interview Insight A common follow-up question is \"Why might parallel merge sort outperform parallel quick sort?\" The answer relates to predictable work distribution. Merge sort always splits evenly, while quick sort's splits depend on pivot selection. Bad pivots create load imbalance that even work stealing can't fully fix. :::\n\n---\n\n## Sequential Baseline\n\nBefore parallelizing, let's establish a clean sequential implementation using Lomuto partition (simpler to explain than Hoare).\n\nimport Tabs from '@theme/Tabs'; import TabItem from '@theme/TabItem';\n\n \n\n\n```java\npublic class SequentialQuickSort {\n\n public static void quickSort(int[] arr) {\n if (arr == null || arr.length <= 1) {\n return;\n }\n quickSort(arr, 0, arr.length - 1);\n }\n\n private static void quickSort(int[] arr, int low, int high) {\n if (low >= high) {\n return;\n }\n\n // Partition and get pivot position\n int pivotIndex = partition(arr, low, high);\n\n // Sort left of pivot\n quickSort(arr, low, pivotIndex - 1);\n\n // Sort right of pivot\n quickSort(arr, pivotIndex + 1, high);\n }\n\n private static int partition(int[] arr, int low, int high) {\n // Use last element as pivot (Lomuto scheme)\n int pivot = arr[high];\n int i = low - 1; // Index of smaller element\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 // Place pivot in correct position\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\n\n \n\n\n```python\ndef quick_sort(arr):\n \"\"\"Sequential quick sort using Lomuto partition.\"\"\"\n if arr is None or len(arr) <= 1:\n return\n _quick_sort(arr, 0, len(arr) - 1)\n\ndef _quick_sort(arr, low, high):\n \"\"\"Recursive quick sort helper.\"\"\"\n if low >= high:\n return\n\n # Partition and get pivot position\n pivot_index = _partition(arr, low, high)\n\n # Sort left of pivot\n _quick_sort(arr, low, pivot_index - 1)\n\n # Sort right of pivot\n _quick_sort(arr, pivot_index + 1, high)\n\ndef _partition(arr, low, high):\n \"\"\"Lomuto partition scheme.\"\"\"\n pivot = arr[high] # Use last element as pivot\n i = low - 1 # Index of smaller element\n\n for j in range(low, high):\n if arr[j] <= pivot:\n i += 1\n arr[i], arr[j] = arr[j], arr[i]\n\n # Place pivot in correct position\n arr[i + 1], arr[high] = arr[high], arr[i + 1]\n return i + 1\n```\n\n\n \n\n\n```cpp\n#include \n#include \n\nclass SequentialQuickSort {\npublic:\n static void quickSort(std::vector& arr) {\n if (arr.size() <= 1) {\n return;\n }\n quickSort(arr, 0, arr.size() - 1);\n }\n\nprivate:\n static void quickSort(std::vector& arr, size_t low, size_t high) {\n if (low >= high) {\n return;\n }\n\n // Partition and get pivot position\n size_t pivotIndex = partition(arr, low, high);\n\n // Sort left of pivot (handle underflow)\n if (pivotIndex > 0) {\n quickSort(arr, low, pivotIndex - 1);\n }\n\n // Sort right of pivot\n quickSort(arr, pivotIndex + 1, high);\n }\n\n static size_t partition(std::vector& arr, size_t low, size_t high) {\n // Use last element as pivot (Lomuto scheme)\n int pivot = arr[high];\n size_t i = low;\n\n for (size_t j = low; j < high; ++j) {\n if (arr[j] <= pivot) {\n std::swap(arr[i], arr[j]);\n ++i;\n }\n }\n\n // Place pivot in correct position\n std::swap(arr[i], arr[high]);\n return i;\n }\n};\n```\n\n\n \n\n\n```csharp\npublic class SequentialQuickSort\n{\n public static void QuickSort(int[] arr)\n {\n if (arr == null || arr.Length <= 1)\n {\n return;\n }\n QuickSort(arr, 0, arr.Length - 1);\n }\n\n private static void QuickSort(int[] arr, int low, int high)\n {\n if (low >= high)\n {\n return;\n }\n\n // Partition and get pivot position\n int pivotIndex = Partition(arr, low, high);\n\n // Sort left of pivot\n QuickSort(arr, low, pivotIndex - 1);\n\n // Sort right of pivot\n QuickSort(arr, pivotIndex + 1, high);\n }\n\n private static int Partition(int[] arr, int low, int high)\n {\n // Use last element as pivot (Lomuto scheme)\n int pivot = arr[high];\n int i = low - 1; // Index of smaller element\n\n for (int j = low; j < high; j++)\n {\n if (arr[j] <= pivot)\n {\n i++;\n Swap(arr, i, j);\n }\n }\n\n // Place pivot in correct position\n Swap(arr, i + 1, high);\n return i + 1;\n }\n\n private static void Swap(int[] arr, int i, int j)\n {\n int temp = arr[i];\n arr[i] = arr[j];\n arr[j] = temp;\n }\n}\n```\n\n\n \n\n\n```go\npackage main\n\n// QuickSort sorts a slice using sequential quick sort with Lomuto partition.\n// Note: Go slices are reference types, so modifications affect the original array.\nfunc QuickSort(arr []int) {\n\tif len(arr) <= 1 {\n\t\treturn\n\t}\n\tquickSort(arr, 0, len(arr)-1)\n}\n\nfunc quickSort(arr []int, low, high int) {\n\tif low >= high {\n\t\treturn\n\t}\n\n\t// Partition and get pivot position\n\tpivotIndex := partition(arr, low, high)\n\n\t// Sort left of pivot\n\tquickSort(arr, low, pivotIndex-1)\n\n\t// Sort right of pivot\n\tquickSort(arr, pivotIndex+1, high)\n}\n\nfunc partition(arr []int, low, high int) int {\n\t// Use last element as pivot (Lomuto scheme)\n\tpivot := arr[high]\n\ti := low - 1 // Index of smaller element\n\n\tfor j := low; j < high; j++ {\n\t\tif arr[j] <= pivot {\n\t\t\ti++\n\t\t\tarr[i], arr[j] = arr[j], arr[i]\n\t\t}\n\t}\n\n\t// Place pivot in correct position\n\tarr[i+1], arr[high] = arr[high], arr[i+1]\n\treturn i + 1\n}\n```\n\n\n \n\n### Identifying Parallelization Opportunities\n\nThe recursion tree reveals where parallelism exists:\n\n\n```mermaid\nflowchart TB\n subgraph Level0[\"Level 0\"]\n P0[\"partition(0..n) - O(n)\"]:::red\n end\n\n subgraph Level1[\"Level 1 - Can run in parallel\"]\n P1L[\"partition(0..k)\"]:::green\n P1R[\"partition(k+1..n)\"]:::green\n end\n\n subgraph Level2[\"Level 2 - Can run in parallel\"]\n P2A[\"partition(...)\"]:::green\n P2B[\"partition(...)\"]:::green\n P2C[\"partition(...)\"]:::green\n P2D[\"partition(...)\"]:::green\n end\n\n P0 --> P1L\n P0 --> P1R\n P1L --> P2A\n P1L --> P2B\n P1R --> P2C\n P1R --> P2D\n\n NOTE[\"Note: Partition sizes vary based on pivot!\"]:::warning\n\n classDef red fill:#ff8787,stroke:#000,color:#000\n classDef green fill:#69db7c,stroke:#000,color:#000\n classDef warning fill:#ffd43b,stroke:#000,color:#000\n```\n\n\nTwo observations:\n\n1. **Independent subproblems:** After partition, left and right subproblems are independent\n2. **Sequential partition:** Each partition must examine all elements in its range\n\nThe critical difference from merge sort: partition happens *before* the recursive calls, and the partition sizes are unpredictable. A bad pivot creates one large and one small partition, leading to load imbalance.\n\n---\n\n## Parallelism Analysis\n\n### Work and Span\n\n**Work (T₁):** Total operations on one processor.\n\nFor quick sort, work is O(n log n) on average. Each element participates in O(log n) partitions on average.\n\n**Span (T∞):** Longest dependency chain.\n\nWith sequential partition:\n\n- Top-level partition: O(n)\n- Recursion depth: O(log n) average, O(n) worst case\n- Each level's partition takes time proportional to its subarray size\n\nIn the average case, the span is dominated by the top-level partition: O(n).\n\nIn the worst case (already sorted array with last-element pivot), span is O(n) just for the partition, and we have O(n) levels, giving O(n²) span.\n\n### Dependency Table\n\n\n| Task | Depends On | Can Parallelize With |\n|------|------------|---------------------|\n| partition(0..n) | None | Nothing (must complete first) |\n| sort(0..k) | partition(0..n) | sort(k+1..n) |\n| sort(k+1..n) | partition(0..n) | sort(0..k) |\n| Final result | All recursions | Nothing |\n\n\nThe key insight: partition creates a synchronization barrier. Until partition completes, we can't start any parallel work.\n\n### Parallelism Comparison\n\n\n| Algorithm | Work | Span (avg) | Parallelism |\n|-----------|------|------------|-------------|\n| Sequential Quick Sort | O(n log n) | O(n log n) | 1 |\n| Parallel Quick Sort (seq partition) | O(n log n) | O(n) | O(log n) |\n| Parallel Merge Sort (seq merge) | O(n log n) | O(n) | O(log n) |\n| Parallel Quick Sort (parallel partition) | O(n log n) | O(log² n) | O(n / log n) |\n\n\nWith sequential partition, parallel quick sort has the same theoretical parallelism as parallel merge sort. But in practice, quick sort often performs worse due to load imbalance from uneven splits.\n\n### Amdahl's Law Impact\n\nIf partition takes 40% of the time in sequential quick sort, the maximum speedup (with infinite processors) is:\n\n\n```shell\nMax Speedup = 1 / 0.4 = 2.5x\n```\n\n\nNo matter how many cores you add, you can't beat 2.5x with sequential partition. This is why parallel partition strategies matter for high core counts.\n\n---\n\n## Approach 1: Thread-per-Subtask (Naive)\n\nThe simplest parallelization: create a thread for each recursive call after partition. This has the same problems as naive parallel merge sort, plus an additional one.\n\n \n\n\n```java\npublic class NaiveParallelQuickSort {\n\n public static void parallelQuickSort(int[] arr) {\n if (arr == null || arr.length <= 1) return;\n parallelQuickSort(arr, 0, arr.length - 1);\n }\n\n private static void parallelQuickSort(int[] arr, int low, int high) {\n if (low >= high) return;\n\n // Partition (sequential)\n int pivotIndex = partition(arr, low, high);\n\n // Create threads for both recursive calls\n Thread leftThread = new Thread(() ->\n parallelQuickSort(arr, low, pivotIndex - 1)\n );\n Thread rightThread = new Thread(() ->\n parallelQuickSort(arr, pivotIndex + 1, high)\n );\n\n leftThread.start();\n rightThread.start();\n\n try {\n leftThread.join();\n rightThread.join();\n } catch (InterruptedException e) {\n Thread.currentThread().interrupt();\n throw new RuntimeException(\"Sorting interrupted\", e);\n }\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\n\n \n\n\n```python\nimport threading\n\ndef naive_parallel_quick_sort(arr):\n \"\"\"Naive parallel quick sort - creates too many threads.\"\"\"\n if arr is None or len(arr) <= 1:\n return\n _naive_parallel_sort(arr, 0, len(arr) - 1)\n\ndef _naive_parallel_sort(arr, low, high):\n \"\"\"Creates a thread for each recursive call.\"\"\"\n if low >= high:\n return\n\n # Partition (sequential)\n pivot_index = _partition(arr, low, high)\n\n # Create threads for both recursive calls\n left_thread = threading.Thread(\n target=_naive_parallel_sort,\n args=(arr, low, pivot_index - 1)\n )\n right_thread = threading.Thread(\n target=_naive_parallel_sort,\n args=(arr, pivot_index + 1, high)\n )\n\n left_thread.start()\n right_thread.start()\n\n left_thread.join()\n right_thread.join()\n\ndef _partition(arr, low, high):\n pivot = arr[high]\n i = low - 1\n\n for j in range(low, high):\n if arr[j] <= pivot:\n i += 1\n arr[i], arr[j] = arr[j], arr[i]\n\n arr[i + 1], arr[high] = arr[high], arr[i + 1]\n return i + 1\n```\n\n\n**Note:** Python's GIL makes this doubly ineffective. Threads don't run in parallel for CPU-bound work, and you still pay thread creation overhead.\n\n \n\n\n```cpp\n#include \n#include \n#include \n\nclass NaiveParallelQuickSort {\npublic:\n static void parallelQuickSort(std::vector& arr) {\n if (arr.size() <= 1) return;\n parallelQuickSort(arr, 0, arr.size() - 1);\n }\n\nprivate:\n static void parallelQuickSort(std::vector& arr, size_t low, size_t high) {\n if (low >= high) return;\n\n // Partition (sequential)\n size_t pivotIndex = partition(arr, low, high);\n\n // Create threads for both recursive calls\n std::thread leftThread([&]() {\n if (pivotIndex > 0) {\n parallelQuickSort(arr, low, pivotIndex - 1);\n }\n });\n std::thread rightThread([&]() {\n parallelQuickSort(arr, pivotIndex + 1, high);\n });\n\n leftThread.join();\n rightThread.join();\n }\n\n static size_t partition(std::vector& arr, size_t low, size_t high) {\n int pivot = arr[high];\n size_t i = low;\n\n for (size_t j = low; j < high; ++j) {\n if (arr[j] <= pivot) {\n std::swap(arr[i], arr[j]);\n ++i;\n }\n }\n\n std::swap(arr[i], arr[high]);\n return i;\n }\n};\n```\n\n\n \n\n\n```csharp\nusing System;\nusing System.Threading.Tasks;\n\npublic class NaiveParallelQuickSort\n{\n public static void ParallelQuickSort(int[] arr)\n {\n if (arr == null || arr.Length <= 1) return;\n ParallelQuickSort(arr, 0, arr.Length - 1);\n }\n\n private static void ParallelQuickSort(int[] arr, int low, int high)\n {\n if (low >= high) return;\n\n // Partition (sequential)\n int pivotIndex = Partition(arr, low, high);\n\n // Create tasks for both recursive calls\n Task leftTask = Task.Run(() =>\n ParallelQuickSort(arr, low, pivotIndex - 1)\n );\n Task rightTask = Task.Run(() =>\n ParallelQuickSort(arr, pivotIndex + 1, high)\n );\n\n Task.WaitAll(leftTask, rightTask);\n }\n\n private static int Partition(int[] arr, int low, int high)\n {\n int pivot = arr[high];\n int i = low - 1;\n\n for (int j = low; j < high; j++)\n {\n if (arr[j] <= pivot)\n {\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 {\n int temp = arr[i];\n arr[i] = arr[j];\n arr[j] = temp;\n }\n}\n```\n\n\n \n\n\n```go\npackage main\n\nimport \"sync\"\n\n// NaiveParallelQuickSort demonstrates the naive approach - creates too many goroutines.\n// This is for educational purposes only. Do not use in production.\nfunc NaiveParallelQuickSort(arr []int) {\n\tif len(arr) <= 1 {\n\t\treturn\n\t}\n\tnaiveParallelSort(arr, 0, len(arr)-1)\n}\n\nfunc naiveParallelSort(arr []int, low, high int) {\n\tif low >= high {\n\t\treturn\n\t}\n\n\t// Partition (sequential)\n\tpivotIndex := partitionNaive(arr, low, high)\n\n\t// Use WaitGroup to synchronize goroutines (Go's fork-join pattern)\n\tvar wg sync.WaitGroup\n\twg.Add(2)\n\n\t// Create goroutines for both recursive calls\n\tgo func() {\n\t\tdefer wg.Done()\n\t\tnaiveParallelSort(arr, low, pivotIndex-1)\n\t}()\n\n\tgo func() {\n\t\tdefer wg.Done()\n\t\tnaiveParallelSort(arr, pivotIndex+1, high)\n\t}()\n\n\t// Wait for both goroutines to complete\n\twg.Wait()\n}\n\nfunc partitionNaive(arr []int, low, high int) int {\n\tpivot := arr[high]\n\ti := low - 1\n\n\tfor j := low; j < high; j++ {\n\t\tif arr[j] <= pivot {\n\t\t\ti++\n\t\t\tarr[i], arr[j] = arr[j], arr[i]\n\t\t}\n\t}\n\n\tarr[i+1], arr[high] = arr[high], arr[i+1]\n\treturn i + 1\n}\n```\n\n\n**Note:** Go's lightweight goroutines handle this better than OS threads, but creating millions of goroutines still causes excessive overhead. The scheduler overhead and stack allocations add up quickly.\n\n \n\n### Thread Explosion (Worse Than Merge Sort)\n\nWith quick sort, thread explosion is even worse because of unbalanced splits:\n\n\n```mermaid\nflowchart TB\n subgraph BadPivot[\"Worst Case: Sorted Array, Last-Element Pivot\"]\n T0[\"n elements → Thread 0\"]:::primary\n T1[\"n-1 elements → Thread 1\"]:::orange\n T2[\"n-2 elements → Thread 2\"]:::orange\n TN[\"1 element → Thread n\"]:::red\n end\n\n T0 --> T1 --> T2 -.-> TN\n\n NOTE[\"O(n) threads created, nearly all work is sequential!\"]:::warning\n\n classDef primary fill:#00ceff,stroke:#000,color:#000\n classDef orange fill:#ffa94d,stroke:#000,color:#000\n classDef red fill:#ff8787,stroke:#000,color:#000\n classDef warning fill:#ffd43b,stroke:#000,color:#000\n```\n\n\nWith merge sort, we always split evenly, so we have at most O(n) threads after log n levels. With quick sort and bad pivots, we create a thread at *every level*, and there can be O(n) levels.\n\n### Analysis\n\n\n| Criteria | Assessment |\n|----------|------------|\n| Correctness | Yes |\n| Efficiency | Very poor |\n| Scalability | Terrible |\n| Worst case | Catastrophic (O(n) threads, O(n²) time) |\n\n\n**Never use this in production.**\n\n---\n\n## Approach 2: Fork-Join with Threshold\n\nThe fix: use a fixed thread pool (Fork-Join) and switch to sequential below a threshold. This is the standard production approach.\n\n \n\n\n```java\nimport java.util.concurrent.*;\n\npublic class ForkJoinQuickSort {\n private static final int THRESHOLD = 8192;\n\n public static void parallelQuickSort(int[] arr) {\n if (arr == null || arr.length <= 1) return;\n\n ForkJoinPool pool = ForkJoinPool.commonPool();\n pool.invoke(new QuickSortTask(arr, 0, arr.length - 1));\n }\n\n public static void parallelQuickSort(int[] arr, int parallelism) {\n if (arr == null || arr.length <= 1) return;\n\n ForkJoinPool pool = new ForkJoinPool(parallelism);\n try {\n pool.invoke(new QuickSortTask(arr, 0, arr.length - 1));\n } finally {\n pool.shutdown();\n }\n }\n\n static class QuickSortTask extends RecursiveAction {\n private final int[] arr;\n private final int low;\n private final int high;\n\n QuickSortTask(int[] arr, int low, int high) {\n this.arr = arr;\n this.low = low;\n this.high = high;\n }\n\n @Override\n protected void compute() {\n // Base case: use sequential sort for small arrays\n if (high - low < THRESHOLD) {\n java.util.Arrays.sort(arr, low, high + 1);\n return;\n }\n\n // Partition\n int pivotIndex = partition();\n\n // Create subtasks\n QuickSortTask leftTask = new QuickSortTask(arr, low, pivotIndex - 1);\n QuickSortTask rightTask = new QuickSortTask(arr, pivotIndex + 1, high);\n\n // Fork left task (adds to work-stealing queue)\n leftTask.fork();\n\n // Compute right task directly\n rightTask.compute();\n\n // Join left task\n leftTask.join();\n }\n\n private int partition() {\n // Median-of-three pivot selection for better balance\n int mid = low + (high - low) / 2;\n\n // Sort low, mid, high\n if (arr[low] > arr[mid]) swap(low, mid);\n if (arr[mid] > arr[high]) swap(mid, high);\n if (arr[low] > arr[mid]) swap(low, mid);\n\n // Use median as pivot, move to high-1\n swap(mid, high - 1);\n int pivot = arr[high - 1];\n\n int i = low;\n int j = high - 1;\n\n while (true) {\n while (arr[++i] < pivot);\n while (arr[--j] > pivot);\n\n if (i >= j) break;\n swap(i, j);\n }\n\n swap(i, high - 1);\n return i;\n }\n\n private void swap(int i, int j) {\n int temp = arr[i];\n arr[i] = arr[j];\n arr[j] = temp;\n }\n }\n\n public static void main(String[] args) {\n int size = 10_000_000;\n int[] arr = new int[size];\n java.util.Random rand = new java.util.Random(42);\n for (int i = 0; i < size; i++) {\n arr[i] = rand.nextInt();\n }\n\n int[] copy = arr.clone();\n\n // Parallel quick sort\n long start = System.currentTimeMillis();\n parallelQuickSort(arr);\n long parallelTime = System.currentTimeMillis() - start;\n\n // Sequential sort\n start = System.currentTimeMillis();\n java.util.Arrays.sort(copy);\n long sequentialTime = System.currentTimeMillis() - start;\n\n System.out.println(\"Parallel (ForkJoin): \" + parallelTime + \" ms\");\n System.out.println(\"Sequential: \" + sequentialTime + \" ms\");\n System.out.printf(\"Speedup: %.2fx%n\", (double) sequentialTime / parallelTime);\n System.out.println(\"Correct: \" + java.util.Arrays.equals(arr, copy));\n }\n}\n```\n\n\n**Output (8-core machine):**\n\n\n```shell\nParallel (ForkJoin): 312 ms\nSequential: 1089 ms\nSpeedup: 3.49x\nCorrect: true\n```\n\n\n \n\n\n```python\nfrom concurrent.futures import ProcessPoolExecutor\nfrom multiprocessing import cpu_count\nimport time\n\nTHRESHOLD = 100_000 # Higher due to process overhead\n\ndef fork_join_quick_sort(arr):\n \"\"\"\n Parallel quick sort using ProcessPoolExecutor.\n Uses a chunked approach due to Python's process overhead.\n \"\"\"\n if arr is None or len(arr) <= 1:\n return\n\n num_workers = cpu_count()\n _parallel_quick_sort_chunked(arr, num_workers)\n\ndef _parallel_quick_sort_chunked(arr, num_workers):\n \"\"\"Divide into chunks, sort in parallel, merge.\"\"\"\n n = len(arr)\n\n if n <= THRESHOLD or num_workers <= 1:\n arr.sort()\n return\n\n # Use sampling to find good split points\n # This approximates what parallel quick sort does\n import random\n sample_size = min(1000, n)\n samples = sorted(random.sample(arr, sample_size))\n\n # Find split points for num_workers chunks\n splits = [samples[i * sample_size // num_workers]\n for i in range(1, num_workers)]\n\n # Partition into buckets based on split points\n buckets = [[] for _ in range(num_workers)]\n for x in arr:\n bucket_idx = 0\n for split in splits:\n if x >= split:\n bucket_idx += 1\n else:\n break\n buckets[bucket_idx].append(x)\n\n # Sort buckets in parallel\n with ProcessPoolExecutor(max_workers=num_workers) as executor:\n sorted_buckets = list(executor.map(sorted, buckets))\n\n # Concatenate back\n idx = 0\n for bucket in sorted_buckets:\n for x in bucket:\n arr[idx] = x\n idx += 1\n\nif __name__ == \"__main__\":\n import random\n\n size = 1_000_000\n arr = [random.randint(0, 1_000_000) for _ in range(size)]\n copy = arr.copy()\n\n # Parallel sort\n start = time.time()\n fork_join_quick_sort(arr)\n parallel_time = time.time() - start\n\n # Sequential sort\n start = time.time()\n copy.sort()\n sequential_time = time.time() - start\n\n print(f\"Parallel: {parallel_time:.3f}s\")\n print(f\"Sequential: {sequential_time:.3f}s\")\n print(f\"Speedup: {sequential_time / parallel_time:.2f}x\")\n print(f\"Correct: {arr == copy}\")\n```\n\n\n**Note:** This is actually a sample sort approximation, which is more practical in Python than true recursive fork-join due to process overhead.\n\n \n\n\n```cpp\n#include \n#include \n#include \n#include \n#include \n\nclass ForkJoinQuickSort {\npublic:\n static constexpr size_t THRESHOLD = 8192;\n\n static void parallelQuickSort(std::vector& arr) {\n if (arr.size() <= 1) return;\n\n unsigned int depth = std::log2(std::thread::hardware_concurrency()) + 1;\n parallelQuickSort(arr, 0, arr.size() - 1, depth);\n }\n\nprivate:\n static void parallelQuickSort(std::vector& arr, size_t low, size_t high,\n unsigned int depth) {\n if (low >= high) return;\n\n // Base case: use sequential sort\n if (high - low < THRESHOLD || depth == 0) {\n std::sort(arr.begin() + low, arr.begin() + high + 1);\n return;\n }\n\n size_t pivotIndex = partition(arr, low, high);\n\n // Launch left half asynchronously\n auto leftFuture = std::async(std::launch::async, [&]() {\n if (pivotIndex > 0) {\n parallelQuickSort(arr, low, pivotIndex - 1, depth - 1);\n }\n });\n\n // Execute right half in current thread\n parallelQuickSort(arr, pivotIndex + 1, high, depth - 1);\n\n // Wait for left half\n leftFuture.get();\n }\n\n static size_t partition(std::vector& arr, size_t low, size_t high) {\n // Median-of-three pivot selection\n size_t mid = low + (high - low) / 2;\n\n if (arr[low] > arr[mid]) std::swap(arr[low], arr[mid]);\n if (arr[mid] > arr[high]) std::swap(arr[mid], arr[high]);\n if (arr[low] > arr[mid]) std::swap(arr[low], arr[mid]);\n\n // Move pivot to high-1\n std::swap(arr[mid], arr[high - 1]);\n int pivot = arr[high - 1];\n\n size_t i = low;\n size_t j = high - 1;\n\n while (true) {\n while (arr[++i] < pivot);\n while (arr[--j] > pivot);\n\n if (i >= j) break;\n std::swap(arr[i], arr[j]);\n }\n\n std::swap(arr[i], arr[high - 1]);\n return i;\n }\n};\n\nint main() {\n size_t size = 10000000;\n std::vector arr(size);\n srand(42);\n for (size_t i = 0; i < size; ++i) {\n arr[i] = rand();\n }\n\n std::vector copy = arr;\n\n // Parallel sort\n auto start = std::chrono::high_resolution_clock::now();\n ForkJoinQuickSort::parallelQuickSort(arr);\n auto end = std::chrono::high_resolution_clock::now();\n auto parallelTime = std::chrono::duration_cast(end - start);\n\n // Sequential sort\n start = std::chrono::high_resolution_clock::now();\n std::sort(copy.begin(), copy.end());\n end = std::chrono::high_resolution_clock::now();\n auto sequentialTime = std::chrono::duration_cast(end - start);\n\n std::cout << \"Parallel: \" << parallelTime.count() << \" ms\" << std::endl;\n std::cout << \"Sequential: \" << sequentialTime.count() << \" ms\" << std::endl;\n std::cout << \"Speedup: \" << (double)sequentialTime.count() / parallelTime.count()\n << \"x\" << std::endl;\n std::cout << \"Correct: \" << (arr == copy ? \"true\" : \"false\") << std::endl;\n\n return 0;\n}\n```\n\n\n \n\n\n```csharp\nusing System;\nusing System.Diagnostics;\nusing System.Linq;\nusing System.Threading.Tasks;\n\npublic class ForkJoinQuickSort\n{\n private const int Threshold = 8192;\n\n public static void ParallelQuickSort(int[] arr)\n {\n if (arr == null || arr.Length <= 1) return;\n\n int maxDepth = (int)Math.Log2(Environment.ProcessorCount) + 1;\n ParallelQuickSort(arr, 0, arr.Length - 1, maxDepth);\n }\n\n public static void ParallelQuickSort(int[] arr, int parallelism)\n {\n if (arr == null || arr.Length <= 1) return;\n\n int maxDepth = (int)Math.Log2(parallelism) + 1;\n ParallelQuickSort(arr, 0, arr.Length - 1, maxDepth);\n }\n\n private static void ParallelQuickSort(int[] arr, int low, int high, int depth)\n {\n if (low >= high) return;\n\n // Base case: use sequential sort for small arrays\n if (high - low < Threshold || depth <= 0)\n {\n Array.Sort(arr, low, high - low + 1);\n return;\n }\n\n // Partition\n int pivotIndex = Partition(arr, low, high);\n\n // Fork left task (run asynchronously)\n Task leftTask = Task.Run(() =>\n ParallelQuickSort(arr, low, pivotIndex - 1, depth - 1)\n );\n\n // Compute right task directly in current thread\n ParallelQuickSort(arr, pivotIndex + 1, high, depth - 1);\n\n // Join left task\n leftTask.Wait();\n }\n\n private static int Partition(int[] arr, int low, int high)\n {\n // Median-of-three pivot selection for better balance\n int mid = low + (high - low) / 2;\n\n // Sort low, mid, high\n if (arr[low] > arr[mid]) Swap(arr, low, mid);\n if (arr[mid] > arr[high]) Swap(arr, mid, high);\n if (arr[low] > arr[mid]) Swap(arr, low, mid);\n\n // Use median as pivot, move to high-1\n Swap(arr, mid, high - 1);\n int pivot = arr[high - 1];\n\n int i = low;\n int j = high - 1;\n\n while (true)\n {\n while (arr[++i] < pivot) { }\n while (arr[--j] > pivot) { }\n\n if (i >= j) break;\n Swap(arr, i, j);\n }\n\n Swap(arr, i, high - 1);\n return i;\n }\n\n private static void Swap(int[] arr, int i, int j)\n {\n int temp = arr[i];\n arr[i] = arr[j];\n arr[j] = temp;\n }\n\n public static void Main(string[] args)\n {\n int size = 10_000_000;\n int[] arr = new int[size];\n Random rand = new Random(42);\n for (int i = 0; i < size; i++)\n {\n arr[i] = rand.Next();\n }\n\n int[] copy = (int[])arr.Clone();\n\n // Parallel quick sort\n Stopwatch sw = Stopwatch.StartNew();\n ParallelQuickSort(arr);\n sw.Stop();\n long parallelTime = sw.ElapsedMilliseconds;\n\n // Sequential sort\n sw.Restart();\n Array.Sort(copy);\n sw.Stop();\n long sequentialTime = sw.ElapsedMilliseconds;\n\n Console.WriteLine($\"Parallel (Fork-Join): {parallelTime} ms\");\n Console.WriteLine($\"Sequential: {sequentialTime} ms\");\n Console.WriteLine($\"Speedup: {(double)sequentialTime / parallelTime:F2}x\");\n Console.WriteLine($\"Correct: {arr.SequenceEqual(copy)}\");\n }\n}\n```\n\n\n**Output (8-core machine):**\n\n\n```shell\nParallel (Fork-Join): 298 ms\nSequential: 1024 ms\nSpeedup: 3.44x\nCorrect: True\n```\n\n\n \n\n\n```go\npackage main\n\nimport (\n\t\"fmt\"\n\t\"math/rand\"\n\t\"runtime\"\n\t\"sort\"\n\t\"sync\"\n\t\"time\"\n)\n\nconst threshold = 8192\n\n// ForkJoinQuickSort sorts using goroutines with threshold-based cutoff.\n// Uses sync.WaitGroup for fork-join synchronization.\nfunc ForkJoinQuickSort(arr []int) {\n\tif len(arr) <= 1 {\n\t\treturn\n\t}\n\t// Limit parallelism depth based on available CPUs\n\tmaxDepth := log2(runtime.NumCPU()) + 1\n\tforkJoinSort(arr, 0, len(arr)-1, maxDepth)\n}\n\n// ForkJoinQuickSortWithParallelism allows specifying the parallelism level.\nfunc ForkJoinQuickSortWithParallelism(arr []int, parallelism int) {\n\tif len(arr) <= 1 {\n\t\treturn\n\t}\n\tmaxDepth := log2(parallelism) + 1\n\tforkJoinSort(arr, 0, len(arr)-1, maxDepth)\n}\n\nfunc forkJoinSort(arr []int, low, high, depth int) {\n\tif low >= high {\n\t\treturn\n\t}\n\n\t// Base case: use sequential sort for small arrays or when depth exhausted\n\tif high-low < threshold || depth <= 0 {\n\t\t// Use Go's built-in sort for the subslice\n\t\tsort.Ints(arr[low : high+1])\n\t\treturn\n\t}\n\n\t// Partition with median-of-three pivot\n\tpivotIndex := partitionMedianOfThree(arr, low, high)\n\n\t// Fork-join pattern using WaitGroup\n\tvar wg sync.WaitGroup\n\twg.Add(1)\n\n\t// Fork: launch left half in a goroutine\n\tgo func() {\n\t\tdefer wg.Done()\n\t\tforkJoinSort(arr, low, pivotIndex-1, depth-1)\n\t}()\n\n\t// Compute right half directly in current goroutine\n\tforkJoinSort(arr, pivotIndex+1, high, depth-1)\n\n\t// Join: wait for left half to complete\n\twg.Wait()\n}\n\nfunc partitionMedianOfThree(arr []int, low, high int) int {\n\t// Median-of-three pivot selection for better balance\n\tmid := low + (high-low)/2\n\n\t// Sort low, mid, high\n\tif arr[low] > arr[mid] {\n\t\tarr[low], arr[mid] = arr[mid], arr[low]\n\t}\n\tif arr[mid] > arr[high] {\n\t\tarr[mid], arr[high] = arr[high], arr[mid]\n\t}\n\tif arr[low] > arr[mid] {\n\t\tarr[low], arr[mid] = arr[mid], arr[low]\n\t}\n\n\t// Use median as pivot, move to high-1\n\tarr[mid], arr[high-1] = arr[high-1], arr[mid]\n\tpivot := arr[high-1]\n\n\ti := low\n\tj := high - 1\n\n\tfor {\n\t\tfor i++; arr[i] < pivot; i++ {\n\t\t}\n\t\tfor j--; arr[j] > pivot; j-- {\n\t\t}\n\n\t\tif i >= j {\n\t\t\tbreak\n\t\t}\n\t\tarr[i], arr[j] = arr[j], arr[i]\n\t}\n\n\tarr[i], arr[high-1] = arr[high-1], arr[i]\n\treturn i\n}\n\n// Helper function to calculate log base 2\nfunc log2(n int) int {\n\tresult := 0\n\tfor n > 1 {\n\t\tn >>= 1\n\t\tresult++\n\t}\n\treturn result\n}\n\nfunc main() {\n\tsize := 10_000_000\n\tarr := make([]int, size)\n\tr := rand.New(rand.NewSource(42))\n\tfor i := 0; i < size; i++ {\n\t\tarr[i] = r.Int()\n\t}\n\n\t// Create a copy for sequential sort\n\tcopyArr := make([]int, size)\n\tcopy(copyArr, arr)\n\n\t// Parallel quick sort\n\tstart := time.Now()\n\tForkJoinQuickSort(arr)\n\tparallelTime := time.Since(start)\n\n\t// Sequential sort\n\tstart = time.Now()\n\tsort.Ints(copyArr)\n\tsequentialTime := time.Since(start)\n\n\t// Verify correctness\n\tcorrect := true\n\tfor i := 0; i < size; i++ {\n\t\tif arr[i] != copyArr[i] {\n\t\t\tcorrect = false\n\t\t\tbreak\n\t\t}\n\t}\n\n\tfmt.Printf(\"Parallel (Fork-Join): %d ms\\n\", parallelTime.Milliseconds())\n\tfmt.Printf(\"Sequential: %d ms\\n\", sequentialTime.Milliseconds())\n\tfmt.Printf(\"Speedup: %.2fx\\n\", float64(sequentialTime)/float64(parallelTime))\n\tfmt.Printf(\"Correct: %v\\n\", correct)\n}\n```\n\n\n**Output (8-core machine):**\n\n\n```shell\nParallel (Fork-Join): 285 ms\nSequential: 1056 ms\nSpeedup: 3.70x\nCorrect: true\n```\n\n\n**Note:** Go's goroutines are lightweight (2KB initial stack vs 1MB for OS threads), making the fork-join pattern very efficient. The `sync.WaitGroup` provides the synchronization needed for the join phase.\n\n \n\n### Work Stealing for Unbalanced Trees\n\nWork stealing is crucial for parallel quick sort. When pivots create uneven splits:\n\n\n```mermaid\nsequenceDiagram\n participant W1 as Worker 1\n participant Q1 as W1's Queue\n participant Q2 as W2's Queue\n participant W2 as Worker 2\n\n Note over W1,W2: Bad pivot: 90/10 split\n\n W1->>Q1: Push sort(0..90K)\n W1->>Q1: Push sort(90K..100K)\n W1->>W1: Pop sort(90K..100K)\n\n Note over W1: Small task, finishes quickly\n\n W2->>Q2: Queue empty\n W2->>Q1: Steal sort(0..90K)\n\n Note over W2: Now W2 has the large task\n\n W2->>Q2: Push sort(0..45K)\n W2->>W2: Work on sort(45K..90K)\n\n Note over W1,W2: Work balances out\n```\n\n\nWithout work stealing, Worker 1 would be stuck with 90% of the work while Worker 2 sits idle. Work stealing redistributes the load.\n\n### Median-of-Three Pivot Selection\n\nGood pivot selection reduces load imbalance:\n\n\n```java\n// Bad: Always use last element\nint pivot = arr[high]; // O(n²) on sorted arrays\n\n// Better: Median of first, middle, last\nint mid = low + (high - low) / 2;\nif (arr[low] > arr[mid]) swap(low, mid);\nif (arr[mid] > arr[high]) swap(mid, high);\nif (arr[low] > arr[mid]) swap(low, mid);\nint pivot = arr[mid]; // More balanced splits\n```\n\n\nMedian-of-three doesn't guarantee balanced splits, but it avoids worst-case behavior on sorted or nearly-sorted input.\n\n### Analysis\n\n\n| Criteria | Assessment |\n|----------|------------|\n| Correctness | Yes |\n| Efficiency | Good |\n| Scalability | Good (work stealing handles imbalance) |\n| Practical use | Recommended for production |\n\n\nThis is a solid production approach. But the partition step is still sequential, limiting speedup. For very large arrays and high core counts, we can do better.\n\n---\n\n## Approach 3: Parallel Partition Strategies\n\nThe partition step is the bottleneck. For the top-level partition of n elements, we do O(n) sequential work. With many cores, this limits speedup. Let's explore how to parallelize partition itself.\n\n### Block Partition Algorithm\n\nThe idea: divide the array into blocks, partition each block locally in parallel, then rearrange globally.\n\n\n```mermaid\nflowchart LR\n subgraph Phase1[\"Phase 1: Local Partition (Parallel)\"]\n direction TB\n B1[\"Block 1: [3,7,1,5]\"]:::primary\n B2[\"Block 2: [8,2,9,4]\"]:::primary\n B3[\"Block 3: [6,0,5,3]\"]:::primary\n\n B1R[\"[3,1│7,5]\"]:::secondary\n B2R[\"[2,4│8,9]\"]:::secondary\n B3R[\"[0,3│6,5]\"]:::secondary\n end\n\n B1 --> B1R\n B2 --> B2R\n B3 --> B3R\n\n subgraph Phase2[\"Phase 2: Count & Prefix Sum\"]\n direction TB\n C1[\"Block 1: 2 small\"]:::orange\n C2[\"Block 2: 2 small\"]:::orange\n C3[\"Block 3: 2 small\"]:::orange\n\n PS[\"Prefix: [0, 2, 4]\"]:::orange\n end\n\n B1R --> C1\n B2R --> C2\n B3R --> C3\n C1 --> PS\n C2 --> PS\n C3 --> PS\n\n subgraph Phase3[\"Phase 3: Global Rearrange (Parallel)\"]\n direction TB\n LEFT[\"Left: [3,1,2,4,0,3]\"]:::green\n RIGHT[\"Right: [7,5,8,9,6,5]\"]:::green\n end\n\n PS --> LEFT\n PS --> RIGHT\n\n classDef primary fill:#00ceff,stroke:#000,color:#000\n classDef secondary fill:#38d9a9,stroke:#000,color:#000\n classDef orange fill:#ffa94d,stroke:#000,color:#000\n classDef green fill:#69db7c,stroke:#000,color:#000\n```\n\n\n**Algorithm Steps:**\n\n1. **Choose pivot** (e.g., median-of-three)\n2. **Divide array into p blocks** (one per thread)\n3. **Local partition:** Each thread partitions its block around the pivot, tracking how many elements go left\n4. **Prefix sum:** Compute where each block's left elements should go in the final array\n5. **Global rearrange:** Each thread moves its elements to their final positions\n\n \n\n\n```java\nimport java.util.concurrent.*;\nimport java.util.concurrent.atomic.AtomicIntegerArray;\n\npublic class ParallelPartitionQuickSort {\n private static final int THRESHOLD = 8192;\n private static final int BLOCK_SIZE = 4096;\n\n public static void parallelQuickSort(int[] arr) {\n if (arr == null || arr.length <= 1) return;\n\n ForkJoinPool pool = ForkJoinPool.commonPool();\n pool.invoke(new QuickSortTask(arr, 0, arr.length - 1, pool));\n }\n\n static class QuickSortTask extends RecursiveAction {\n private final int[] arr;\n private final int low;\n private final int high;\n private final ForkJoinPool pool;\n\n QuickSortTask(int[] arr, int low, int high, ForkJoinPool pool) {\n this.arr = arr;\n this.low = low;\n this.high = high;\n this.pool = pool;\n }\n\n @Override\n protected void compute() {\n int length = high - low + 1;\n\n if (length < THRESHOLD) {\n java.util.Arrays.sort(arr, low, high + 1);\n return;\n }\n\n // Use parallel partition for large arrays\n int pivotIndex;\n if (length > 100_000) {\n pivotIndex = parallelPartition();\n } else {\n pivotIndex = sequentialPartition();\n }\n\n QuickSortTask leftTask = new QuickSortTask(arr, low, pivotIndex - 1, pool);\n QuickSortTask rightTask = new QuickSortTask(arr, pivotIndex + 1, high, pool);\n\n leftTask.fork();\n rightTask.compute();\n leftTask.join();\n }\n\n private int parallelPartition() {\n int length = high - low + 1;\n int numBlocks = Math.min(pool.getParallelism(), length / BLOCK_SIZE);\n if (numBlocks < 2) return sequentialPartition();\n\n // Choose pivot using median-of-three\n int pivot = choosePivot();\n\n // Step 1: Count elements <= pivot in each block (parallel)\n int[] leftCounts = new int[numBlocks];\n int blockSize = length / numBlocks;\n\n CountDownLatch countLatch = new CountDownLatch(numBlocks);\n\n for (int b = 0; b < numBlocks; b++) {\n final int block = b;\n int blockStart = low + block * blockSize;\n int blockEnd = (block == numBlocks - 1) ? high : blockStart + blockSize - 1;\n\n pool.execute(() -> {\n int count = 0;\n for (int i = blockStart; i <= blockEnd; i++) {\n if (arr[i] <= pivot) count++;\n }\n leftCounts[block] = count;\n countLatch.countDown();\n });\n }\n\n try {\n countLatch.await();\n } catch (InterruptedException e) {\n Thread.currentThread().interrupt();\n }\n\n // Step 2: Prefix sum to get destination indices\n int[] leftStarts = new int[numBlocks];\n leftStarts[0] = low;\n for (int b = 1; b < numBlocks; b++) {\n leftStarts[b] = leftStarts[b - 1] + leftCounts[b - 1];\n }\n int totalLeft = leftStarts[numBlocks - 1] + leftCounts[numBlocks - 1];\n\n // Step 3: Rearrange using temporary array (parallel)\n int[] temp = new int[length];\n int[] rightStarts = new int[numBlocks];\n rightStarts[0] = totalLeft;\n for (int b = 1; b < numBlocks; b++) {\n int rightCount = (b == numBlocks - 1 ? high - (low + b * blockSize) + 1\n : blockSize) - leftCounts[b - 1];\n rightStarts[b] = rightStarts[b - 1] + rightCount;\n }\n\n CountDownLatch arrangeLatch = new CountDownLatch(numBlocks);\n\n for (int b = 0; b < numBlocks; b++) {\n final int block = b;\n int blockStart = low + block * blockSize;\n int blockEnd = (block == numBlocks - 1) ? high : blockStart + blockSize - 1;\n\n pool.execute(() -> {\n int leftIdx = leftStarts[block];\n int rightIdx = totalLeft + (blockStart - low) - leftStarts[block]\n + (block > 0 ? leftCounts[block - 1] : 0);\n\n for (int i = blockStart; i <= blockEnd; i++) {\n if (arr[i] <= pivot) {\n temp[leftIdx++ - low] = arr[i];\n } else {\n temp[rightIdx++ - low] = arr[i];\n }\n }\n arrangeLatch.countDown();\n });\n }\n\n try {\n arrangeLatch.await();\n } catch (InterruptedException e) {\n Thread.currentThread().interrupt();\n }\n\n // Copy back\n System.arraycopy(temp, 0, arr, low, length);\n\n return low + totalLeft - 1;\n }\n\n private int sequentialPartition() {\n int mid = low + (high - low) / 2;\n\n if (arr[low] > arr[mid]) swap(low, mid);\n if (arr[mid] > arr[high]) swap(mid, high);\n if (arr[low] > arr[mid]) swap(low, mid);\n\n swap(mid, high - 1);\n int pivot = arr[high - 1];\n\n int i = low;\n int j = high - 1;\n\n while (true) {\n while (arr[++i] < pivot);\n while (arr[--j] > pivot);\n\n if (i >= j) break;\n swap(i, j);\n }\n\n swap(i, high - 1);\n return i;\n }\n\n private int choosePivot() {\n int mid = low + (high - low) / 2;\n\n if (arr[low] > arr[mid]) swap(low, mid);\n if (arr[mid] > arr[high]) swap(mid, high);\n if (arr[low] > arr[mid]) swap(low, mid);\n\n return arr[mid];\n }\n\n private void swap(int i, int j) {\n int temp = arr[i];\n arr[i] = arr[j];\n arr[j] = temp;\n }\n }\n}\n```\n\n\n \n\n\n```csharp\nusing System;\nusing System.Threading;\nusing System.Threading.Tasks;\n\npublic class ParallelPartitionQuickSort\n{\n private const int Threshold = 8192;\n private const int BlockSize = 4096;\n\n public static void ParallelQuickSort(int[] arr)\n {\n if (arr == null || arr.Length <= 1) return;\n\n int parallelism = Environment.ProcessorCount;\n QuickSortTask(arr, 0, arr.Length - 1, parallelism);\n }\n\n private static void QuickSortTask(int[] arr, int low, int high, int parallelism)\n {\n int length = high - low + 1;\n\n if (length < Threshold)\n {\n Array.Sort(arr, low, length);\n return;\n }\n\n // Use parallel partition for large arrays\n int pivotIndex;\n if (length > 100_000)\n {\n pivotIndex = ParallelPartition(arr, low, high, parallelism);\n }\n else\n {\n pivotIndex = SequentialPartition(arr, low, high);\n }\n\n // Fork left task\n Task leftTask = Task.Run(() =>\n QuickSortTask(arr, low, pivotIndex - 1, parallelism)\n );\n\n // Compute right task directly\n QuickSortTask(arr, pivotIndex + 1, high, parallelism);\n\n // Join left task\n leftTask.Wait();\n }\n\n private static int ParallelPartition(int[] arr, int low, int high, int parallelism)\n {\n int length = high - low + 1;\n int numBlocks = Math.Min(parallelism, length / BlockSize);\n if (numBlocks < 2) return SequentialPartition(arr, low, high);\n\n // Choose pivot using median-of-three\n int pivot = ChoosePivot(arr, low, high);\n\n // Step 1: Count elements <= pivot in each block (parallel)\n int[] leftCounts = new int[numBlocks];\n int blockSize = length / numBlocks;\n\n Parallel.For(0, numBlocks, block =>\n {\n int blockStart = low + block * blockSize;\n int blockEnd = (block == numBlocks - 1) ? high : blockStart + blockSize - 1;\n\n int count = 0;\n for (int i = blockStart; i <= blockEnd; i++)\n {\n if (arr[i] <= pivot) count++;\n }\n leftCounts[block] = count;\n });\n\n // Step 2: Prefix sum to get destination indices\n int[] leftStarts = new int[numBlocks];\n leftStarts[0] = low;\n for (int b = 1; b < numBlocks; b++)\n {\n leftStarts[b] = leftStarts[b - 1] + leftCounts[b - 1];\n }\n int totalLeft = leftStarts[numBlocks - 1] + leftCounts[numBlocks - 1];\n\n // Step 3: Rearrange using temporary array (parallel)\n int[] temp = new int[length];\n\n Parallel.For(0, numBlocks, block =>\n {\n int blockStart = low + block * blockSize;\n int blockEnd = (block == numBlocks - 1) ? high : blockStart + blockSize - 1;\n\n int leftIdx = leftStarts[block] - low;\n int rightIdx = totalLeft + (blockStart - low) - (leftStarts[block] - low);\n\n for (int i = blockStart; i <= blockEnd; i++)\n {\n if (arr[i] <= pivot)\n {\n temp[leftIdx++] = arr[i];\n }\n else\n {\n temp[rightIdx++] = arr[i];\n }\n }\n });\n\n // Copy back\n Array.Copy(temp, 0, arr, low, length);\n\n return low + totalLeft - 1;\n }\n\n private static int SequentialPartition(int[] arr, int low, int high)\n {\n int mid = low + (high - low) / 2;\n\n if (arr[low] > arr[mid]) Swap(arr, low, mid);\n if (arr[mid] > arr[high]) Swap(arr, mid, high);\n if (arr[low] > arr[mid]) Swap(arr, low, mid);\n\n Swap(arr, mid, high - 1);\n int pivot = arr[high - 1];\n\n int i = low;\n int j = high - 1;\n\n while (true)\n {\n while (arr[++i] < pivot) { }\n while (arr[--j] > pivot) { }\n\n if (i >= j) break;\n Swap(arr, i, j);\n }\n\n Swap(arr, i, high - 1);\n return i;\n }\n\n private static int ChoosePivot(int[] arr, int low, int high)\n {\n int mid = low + (high - low) / 2;\n\n if (arr[low] > arr[mid]) Swap(arr, low, mid);\n if (arr[mid] > arr[high]) Swap(arr, mid, high);\n if (arr[low] > arr[mid]) Swap(arr, low, mid);\n\n return arr[mid];\n }\n\n private static void Swap(int[] arr, int i, int j)\n {\n int temp = arr[i];\n arr[i] = arr[j];\n arr[j] = temp;\n }\n}\n```\n\n\n \n\n\n```go\npackage main\n\nimport (\n\t\"runtime\"\n\t\"sort\"\n\t\"sync\"\n)\n\nconst (\n\tthresholdParallel = 8192\n\tblockSize = 4096\n)\n\n// ParallelPartitionQuickSort uses parallel partition for large arrays.\nfunc ParallelPartitionQuickSort(arr []int) {\n\tif len(arr) <= 1 {\n\t\treturn\n\t}\n\tparallelism := runtime.NumCPU()\n\tparallelPartitionSort(arr, 0, len(arr)-1, parallelism)\n}\n\nfunc parallelPartitionSort(arr []int, low, high, parallelism int) {\n\tlength := high - low + 1\n\n\tif length < thresholdParallel {\n\t\tsort.Ints(arr[low : high+1])\n\t\treturn\n\t}\n\n\t// Use parallel partition for large arrays\n\tvar pivotIndex int\n\tif length > 100_000 {\n\t\tpivotIndex = parallelPartition(arr, low, high, parallelism)\n\t} else {\n\t\tpivotIndex = sequentialPartitionPP(arr, low, high)\n\t}\n\n\t// Fork-join for recursive calls\n\tvar wg sync.WaitGroup\n\twg.Add(1)\n\n\tgo func() {\n\t\tdefer wg.Done()\n\t\tparallelPartitionSort(arr, low, pivotIndex-1, parallelism)\n\t}()\n\n\tparallelPartitionSort(arr, pivotIndex+1, high, parallelism)\n\twg.Wait()\n}\n\nfunc parallelPartition(arr []int, low, high, parallelism int) int {\n\tlength := high - low + 1\n\tnumBlocks := min(parallelism, length/blockSize)\n\tif numBlocks < 2 {\n\t\treturn sequentialPartitionPP(arr, low, high)\n\t}\n\n\t// Choose pivot using median-of-three\n\tpivot := choosePivot(arr, low, high)\n\n\t// Step 1: Count elements <= pivot in each block (parallel)\n\tleftCounts := make([]int, numBlocks)\n\tblockSz := length / numBlocks\n\n\tvar countWg sync.WaitGroup\n\tcountWg.Add(numBlocks)\n\n\tfor b := 0; b < numBlocks; b++ {\n\t\tgo func(block int) {\n\t\t\tdefer countWg.Done()\n\t\t\tblockStart := low + block*blockSz\n\t\t\tblockEnd := blockStart + blockSz - 1\n\t\t\tif block == numBlocks-1 {\n\t\t\t\tblockEnd = high\n\t\t\t}\n\n\t\t\tcount := 0\n\t\t\tfor i := blockStart; i <= blockEnd; i++ {\n\t\t\t\tif arr[i] <= pivot {\n\t\t\t\t\tcount++\n\t\t\t\t}\n\t\t\t}\n\t\t\tleftCounts[block] = count\n\t\t}(b)\n\t}\n\tcountWg.Wait()\n\n\t// Step 2: Prefix sum to get destination indices\n\tleftStarts := make([]int, numBlocks)\n\tleftStarts[0] = low\n\tfor b := 1; b < numBlocks; b++ {\n\t\tleftStarts[b] = leftStarts[b-1] + leftCounts[b-1]\n\t}\n\ttotalLeft := leftStarts[numBlocks-1] + leftCounts[numBlocks-1]\n\n\t// Step 3: Rearrange using temporary slice (parallel)\n\ttemp := make([]int, length)\n\n\tvar arrangeWg sync.WaitGroup\n\tarrangeWg.Add(numBlocks)\n\n\tfor b := 0; b < numBlocks; b++ {\n\t\tgo func(block int) {\n\t\t\tdefer arrangeWg.Done()\n\t\t\tblockStart := low + block*blockSz\n\t\t\tblockEnd := blockStart + blockSz - 1\n\t\t\tif block == numBlocks-1 {\n\t\t\t\tblockEnd = high\n\t\t\t}\n\n\t\t\tleftIdx := leftStarts[block] - low\n\t\t\trightIdx := totalLeft + (blockStart - low) - (leftStarts[block] - low)\n\n\t\t\tfor i := blockStart; i <= blockEnd; i++ {\n\t\t\t\tif arr[i] <= pivot {\n\t\t\t\t\ttemp[leftIdx] = arr[i]\n\t\t\t\t\tleftIdx++\n\t\t\t\t} else {\n\t\t\t\t\ttemp[rightIdx] = arr[i]\n\t\t\t\t\trightIdx++\n\t\t\t\t}\n\t\t\t}\n\t\t}(b)\n\t}\n\tarrangeWg.Wait()\n\n\t// Copy back to original array\n\tcopy(arr[low:high+1], temp)\n\n\treturn low + totalLeft - 1\n}\n\nfunc sequentialPartitionPP(arr []int, low, high int) int {\n\tmid := low + (high-low)/2\n\n\tif arr[low] > arr[mid] {\n\t\tarr[low], arr[mid] = arr[mid], arr[low]\n\t}\n\tif arr[mid] > arr[high] {\n\t\tarr[mid], arr[high] = arr[high], arr[mid]\n\t}\n\tif arr[low] > arr[mid] {\n\t\tarr[low], arr[mid] = arr[mid], arr[low]\n\t}\n\n\tarr[mid], arr[high-1] = arr[high-1], arr[mid]\n\tpivot := arr[high-1]\n\n\ti := low\n\tj := high - 1\n\n\tfor {\n\t\tfor i++; arr[i] < pivot; i++ {\n\t\t}\n\t\tfor j--; arr[j] > pivot; j-- {\n\t\t}\n\n\t\tif i >= j {\n\t\t\tbreak\n\t\t}\n\t\tarr[i], arr[j] = arr[j], arr[i]\n\t}\n\n\tarr[i], arr[high-1] = arr[high-1], arr[i]\n\treturn i\n}\n\nfunc choosePivot(arr []int, low, high int) int {\n\tmid := low + (high-low)/2\n\n\tif arr[low] > arr[mid] {\n\t\tarr[low], arr[mid] = arr[mid], arr[low]\n\t}\n\tif arr[mid] > arr[high] {\n\t\tarr[mid], arr[high] = arr[high], arr[mid]\n\t}\n\tif arr[low] > arr[mid] {\n\t\tarr[low], arr[mid] = arr[mid], arr[low]\n\t}\n\n\treturn arr[mid]\n}\n\nfunc min(a, b int) int {\n\tif a < b {\n\t\treturn a\n\t}\n\treturn b\n}\n```\n\n\n**Note:** Go's goroutines and `sync.WaitGroup` provide an elegant way to implement the parallel counting and rearrangement phases. The three-phase approach (count, prefix sum, rearrange) naturally maps to Go's concurrency primitives.\n\n \n\n### Three-Way Partition (Dutch National Flag)\n\nWhen the array has many duplicates, standard partition is inefficient. Three-way partition divides into three regions: less than, equal to, and greater than pivot.\n\n\n```mermaid\nflowchart LR\n subgraph Input[\"Input with Duplicates\"]\n I[\"[5, 2, 5, 8, 5, 1, 5, 9]\"]:::primary\n end\n\n subgraph ThreeWay[\"Three-Way Partition (pivot=5)\"]\n LT[\"< 5: [2, 1]\"]:::green\n EQ[\"= 5: [5, 5, 5, 5]\"]:::orange\n GT[\"> 5: [8, 9]\"]:::red\n end\n\n Input --> ThreeWay\n\n subgraph Recurse[\"Only Recurse on < and >\"]\n R1[\"Sort [2, 1]\"]:::secondary\n R2[\"Skip [5, 5, 5, 5]\"]:::teal\n R3[\"Sort [8, 9]\"]:::secondary\n end\n\n ThreeWay --> Recurse\n\n classDef primary fill:#00ceff,stroke:#000,color:#000\n classDef secondary fill:#38d9a9,stroke:#000,color:#000\n classDef green fill:#69db7c,stroke:#000,color:#000\n classDef orange fill:#ffa94d,stroke:#000,color:#000\n classDef red fill:#ff8787,stroke:#000,color:#000\n classDef teal fill:#3bc9db,stroke:#000,color:#000\n```\n\n\nThe key insight: elements equal to the pivot are already in their final position. We don't recurse on them, which can dramatically reduce work when there are many duplicates.\n\n\n```java\nprivate int[] threeWayPartition(int[] arr, int low, int high) {\n int pivot = arr[low + (high - low) / 2];\n\n int lt = low; // arr[low..lt-1] < pivot\n int gt = high; // arr[gt+1..high] > pivot\n int i = low; // arr[lt..i-1] == pivot\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 // Return bounds of equal region\n return new int[]{lt, gt}; // arr[lt..gt] == pivot\n}\n```\n\n\n### Sample Sort (High Parallelism)\n\nFor very high core counts (32+), even parallel partition can be a bottleneck. Sample sort provides better parallelism:\n\n1. **Sample:** Pick p-1 random elements as splitters\n2. **Sort splitters:** Quick sort the splitters\n3. **Bucket:** Each element goes to one of p buckets based on splitters\n4. **Parallel sort buckets:** Each processor sorts one bucket\n5. **Concatenate:** Buckets are already in order\n\n\n```mermaid\nflowchart TB\n subgraph Sample[\"1. Sample & Sort Splitters\"]\n S[\"Pick 3 samples: [35, 67, 12]\"]:::primary\n SS[\"Sorted: [12, 35, 67]\"]:::secondary\n end\n\n subgraph Bucket[\"2. Bucket Elements (Parallel)\"]\n B1[\"< 12\"]:::green\n B2[\"12-35\"]:::orange\n B3[\"35-67\"]:::yellow\n B4[\"> 67\"]:::red\n end\n\n subgraph Sort[\"3. Sort Buckets (Parallel)\"]\n S1[\"Sort B1\"]:::green\n S2[\"Sort B2\"]:::orange\n S3[\"Sort B3\"]:::yellow\n S4[\"Sort B4\"]:::red\n end\n\n subgraph Result[\"4. Concatenate\"]\n R[\"Sorted array\"]:::purple\n end\n\n Sample --> Bucket --> Sort --> Result\n\n classDef primary fill:#00ceff,stroke:#000,color:#000\n classDef secondary fill:#38d9a9,stroke:#000,color:#000\n classDef green fill:#69db7c,stroke:#000,color:#000\n classDef orange fill:#ffa94d,stroke:#000,color:#000\n classDef yellow fill:#ffd43b,stroke:#000,color:#000\n classDef red fill:#ff8787,stroke:#000,color:#000\n classDef purple fill:#9775fa,stroke:#000,color:#000\n```\n\n\nSample sort is what Intel TBB's `parallel_sort` uses internally. It's more complex but provides O(n/p) span when splitters are well-chosen.\n\n---\n\n## Performance Analysis\n\n### Theoretical vs. Actual Speedup\n\n\n| Cores | Sequential Partition | Block Partition | Sample Sort |\n|-------|---------------------|-----------------|-------------|\n| 1 | 1.0x | 1.0x | 1.0x |\n| 2 | 1.7x | 1.8x | 1.9x |\n| 4 | 2.8x | 3.2x | 3.5x |\n| 8 | 3.5x | 4.5x | 5.5x |\n| 16 | 4.0x | 6.0x | 8.5x |\n| 32 | 4.2x | 7.5x | 13x |\n\n\nWith sequential partition, speedup plateaus around 4x regardless of core count. Block partition helps, but the real gains come from sample sort on many-core systems.\n\n### Why Quick Sort Scales Differently Than Merge Sort\n\n\n```mermaid\nflowchart LR\n subgraph QuickSort[\"Quick Sort\"]\n QP[\"Partition varies\"]:::orange\n QW[\"Work imbalance\"]:::red\n QC[\"Cache friendly\"]:::green\n end\n\n subgraph MergeSort[\"Merge Sort\"]\n MP[\"Merge is fixed O(n)\"]:::orange\n MW[\"Work balanced\"]:::green\n MC[\"Memory intensive\"]:::red\n end\n\n QP --> QW\n MP --> MW\n\n classDef green fill:#69db7c,stroke:#000,color:#000\n classDef orange fill:#ffa94d,stroke:#000,color:#000\n classDef red fill:#ff8787,stroke:#000,color:#000\n```\n\n\n**Merge sort advantages:**\n\n- Predictable split (always 50/50)\n- Consistent load balancing\n- Parallelization is deterministic\n\n**Quick sort advantages:**\n\n- In-place (no O(n) extra memory)\n- Better cache locality\n- Faster in practice for small arrays\n\nFor parallel sorting, merge sort's predictability often wins. That's why Java's `Arrays.parallelSort()` uses merge sort, not quick sort.\n\n### Benchmark Template\n\n\n```java\npublic class QuickSortBenchmark {\n\n public static void main(String[] args) {\n int[] sizes = {100_000, 1_000_000, 10_000_000, 100_000_000};\n\n System.out.println(\"Size\\t\\tSequential\\tParallel\\tSpeedup\");\n System.out.println(\"----\\t\\t----------\\t--------\\t-------\");\n\n for (int size : sizes) {\n int[] arr = new int[size];\n java.util.Random rand = new java.util.Random(42);\n for (int i = 0; i < size; i++) {\n arr[i] = rand.nextInt();\n }\n\n // Warm up\n int[] warmup = arr.clone();\n ForkJoinQuickSort.parallelQuickSort(warmup);\n\n // Sequential timing\n int[] seqArr = arr.clone();\n long seqStart = System.nanoTime();\n java.util.Arrays.sort(seqArr);\n long seqTime = System.nanoTime() - seqStart;\n\n // Parallel timing\n int[] parArr = arr.clone();\n long parStart = System.nanoTime();\n ForkJoinQuickSort.parallelQuickSort(parArr);\n long parTime = System.nanoTime() - parStart;\n\n // Verify\n if (!java.util.Arrays.equals(seqArr, parArr)) {\n System.err.println(\"ERROR: Results don't match!\");\n continue;\n }\n\n double speedup = (double) seqTime / parTime;\n System.out.printf(\"%,d\\t\\t%,d ms\\t\\t%,d ms\\t\\t%.2fx%n\",\n size, seqTime / 1_000_000, parTime / 1_000_000, speedup);\n }\n }\n}\n```\n\n\n---\n\n## Quick Sort vs. Merge Sort: When to Use Which\n\n### Comparison Table\n\n\n| Aspect | Parallel Quick Sort | Parallel Merge Sort |\n|--------|---------------------|---------------------|\n| **Stability** | Not stable | Stable |\n| **Space** | O(log n) stack | O(n) auxiliary |\n| **Worst case** | O(n²) possible | O(n log n) guaranteed |\n| **Bottleneck** | Partition (hard to parallelize) | Merge (easier to parallelize) |\n| **Load balance** | Depends on pivot | Always even splits |\n| **Cache locality** | Excellent | Good |\n| **In-place** | Yes | No |\n\n\n### Decision Tree\n\n\n```mermaid\nflowchart TD\n START[\"Need parallel sort?\"]:::primary\n\n Q1{\"Stability required?\"}:::yellow\n Q2{\"Memory constrained?\"}:::yellow\n Q3{\"Many duplicates?\"}:::yellow\n Q4{\"High core count (16+)?\"}:::yellow\n\n MERGE[\"Use Parallel Merge Sort\"]:::green\n QSORT[\"Use Parallel Quick Sort\"]:::green\n SAMPLE[\"Use Sample Sort\"]:::green\n THREE[\"Use 3-Way Quick Sort\"]:::green\n\n START --> Q1\n Q1 -->|\"Yes\"| MERGE\n Q1 -->|\"No\"| Q2\n Q2 -->|\"Yes\"| QSORT\n Q2 -->|\"No\"| Q3\n Q3 -->|\"Yes\"| THREE\n Q3 -->|\"No\"| Q4\n Q4 -->|\"Yes\"| SAMPLE\n Q4 -->|\"No\"| MERGE\n\n classDef primary fill:#00ceff,stroke:#000,color:#000\n classDef yellow fill:#ffd43b,stroke:#000,color:#000\n classDef green fill:#69db7c,stroke:#000,color:#000\n```\n\n\n### Practical Recommendation\n\nFor most applications, use the standard library's parallel sort:\n\n- **Java:** `Arrays.parallelSort()` uses merge sort internally\n- **C++:** `std::sort(std::execution::par, ...)` implementation varies\n- **Python:** For numeric data, use NumPy\n\nIf you need quick sort specifically (memory constraints, cache behavior), use Fork-Join with median-of-three pivot selection and a reasonable threshold (8K-16K elements).\n\n---\n\n## Interview Questions\n\n**Q1: What is the work-span analysis for parallel quick sort?**\n\n**A:** For parallel quick sort with sequential partition:\n\n- **Work T₁ = O(n log n) average:** Same as sequential. We do the same operations, just distributed. In the worst case (bad pivots), work degrades to O(n²).\n\n- **Span T∞ = O(n) average:** The top-level partition takes O(n) time. Even with parallel recursion, we can't start sorting until partition completes. Recursion adds O(log n) levels, each dominated by its partition step. The critical path is: partition at each level of the tree along the deepest branch.\n\n- **Parallelism T₁/T∞ = O(log n) average:** Similar to merge sort with sequential merge. Maximum useful processors is O(log n).\n\nWith parallel partition:\n\n- Span reduces to O(log² n) average: O(log n) recursion depth, each with O(log n) partition span\n- Parallelism increases to O(n / log n)\n\nThe worst case (sorted array with last-element pivot) gives O(n²) work and O(n²) span without proper pivot selection.\n\n---\n\n**Q2: Why is partition harder to parallelize than merge?**\n\n**A:** Several factors make partition harder:\n\n1. **Write conflicts:** Partition moves elements to opposite ends of the array. Multiple threads writing to the same region cause conflicts. Merge writes to a separate output array with predictable positions.\n\n1. **Data-dependent positions:** In partition, where an element goes depends on its comparison with the pivot. We don't know final positions until we scan. In merge, positions are predictable from the input structure.\n\n1. **Single pass requirement:** Standard partition algorithms (Lomuto, Hoare) scan the array once, maintaining invariants. Parallelizing this requires either multiple passes or complex synchronization.\n\n1. **In-place nature:** Quick sort's space advantage comes from in-place partition. Parallel partition often requires auxiliary space, negating this benefit.\n\n1. **Prefix sum dependency:** To know where thread T's elements should go, we need counts from all preceding threads, creating a sequential dependency.\n\nBlock partition works around these by: (1) local independent passes, (2) prefix sum for positions, (3) parallel global rearrangement. But it adds overhead and complexity.\n\n---\n\n**Q3: Explain the block partition algorithm.**\n\n**A:** Block partition parallelizes the partition step through three phases:\n\n**Phase 1: Local Classification (Parallel)**\n\n- Divide array into p blocks (one per thread)\n- Each thread scans its block, counting elements ≤ pivot\n- Each thread locally partitions its block (elements ≤ pivot at start, > pivot at end)\n- Store counts: leftCount[i] = number of elements ≤ pivot in block i\n\n**Phase 2: Prefix Sum (Sequential)**\n\n- Compute prefix sums to determine destination positions\n- leftStart[i] = sum of leftCount[0..i-1]\n- This tells each thread where its \"small\" elements should go\n\n**Phase 3: Global Rearrangement (Parallel)**\n\n- Each thread moves its elements to final positions using computed offsets\n- Thread i writes its small elements starting at leftStart[i]\n- Thread i writes its large elements starting at appropriate offset\n\n**Complexity:**\n\n- Work: O(n) - each element examined constant times\n- Span: O(n/p + p) - parallel scan + prefix sum + parallel move\n- For p = O(n^ε) for small ε, span is O(n/p)\n\n**Trade-offs:**\n\n- Requires O(n) auxiliary space (or complex in-place swapping)\n- Overhead makes it worthwhile only for large arrays (>100K elements)\n- Multiple passes over data hurt cache performance\n\n---\n\n**Q4: How does pivot selection affect parallel performance?**\n\n**A:** Pivot selection critically affects load balance:\n\n**Bad pivot (extreme value):**\n\n- Creates n-1 : 1 split\n- One thread gets almost all the work\n- Work stealing helps but can't fully compensate\n- Span approaches O(n) at that level\n\n**Good pivot (median):**\n\n- Creates n/2 : n/2 split\n- Work divides evenly between threads\n- Span is O(n/2) at that level\n- Recursion depth is O(log n)\n\n**Pivot selection strategies:**\n\n\n| Strategy | Expected Split | Overhead | Worst Case |\n|----------|---------------|----------|------------|\n| Last element | Uniform if random | O(1) | Sorted input |\n| Random | Uniform | O(1) | Very unlikely bad |\n| Median-of-three | Better than random | O(1) | Still possible |\n| Median-of-medians | O(n) guaranteed | O(n) | None |\n| Sample sort | Near-equal buckets | O(k log k) | Very unlikely |\n\n\n**Recommendation:** Use median-of-three for simple parallel quick sort. For high core counts (16+), use sample sort with oversampling.\n\nFor interview, emphasize: random or median-of-three gives O(n log n) expected time, eliminates worst-case for practical inputs, adds negligible overhead.\n\n---\n\n**Q5: Compare parallel quick sort vs. parallel merge sort. When would you choose each?**\n\n**A:**\n\n\n| Factor | Choose Quick Sort | Choose Merge Sort |\n|--------|-------------------|-------------------|\n| Memory | Constrained (O(log n) vs O(n)) | Available |\n| Stability | Not needed | Required |\n| Input pattern | Random data | Unknown/adversarial |\n| Duplicates | Few (or use 3-way) | Many |\n| Core count | 2-8 cores | 16+ cores |\n| Predictability | Variance acceptable | Consistent time needed |\n| Data location | In-place required | Copy acceptable |\n\n\n**For parallel execution specifically:**\n\nMerge sort is generally preferred because:\n\n1. Predictable 50/50 splits enable better load balancing\n2. Merge is more naturally parallelizable than partition\n3. No worst-case O(n²) risk\n4. Work stealing is less necessary (work already balanced)\n\nQuick sort is preferred when:\n\n1. Memory is critical (embedded systems)\n2. Cache behavior matters more than parallelism\n3. Data is known to be random (no adversarial input)\n4. Core count is low (2-4), where load imbalance matters less\n\n**Production reality:** Java's `Arrays.parallelSort()` uses merge sort. Intel TBB's `parallel_sort` uses sample sort (a parallel-friendly quick sort variant). Choose based on your constraints.\n\n---\n\n**Q6: When would you NOT parallelize quick sort?**\n\n**A:** Don't parallelize quick sort when:\n\n1. **Small arrays (<10K elements):** Fork-join overhead exceeds benefits. Sequential quick sort is cache-efficient and fast for small data.\n\n1. **Few cores (2 cores):** Maximum speedup is ~1.8x. Given overhead, you might see 1.3-1.5x, barely worth the complexity.\n\n1. **Sorted or nearly-sorted input:** Without proper pivot selection, you risk O(n²) behavior. If input patterns are unknown, merge sort is safer.\n\n1. **Stability required:** Quick sort isn't stable. No parallel variant changes this. Use merge sort instead.\n\n1. **Many duplicates:** Standard quick sort degenerates with duplicates. Use three-way partition (Dutch National Flag) or switch to merge sort.\n\n1. **Real-time requirements:** Quick sort has variable timing (depends on pivots). Merge sort provides more consistent performance.\n\n1. **Memory-mapped or distributed data:** Partition requires random access patterns. Merge sort's sequential access works better for external sorting.\n\n1. **Already I/O bound:** If reading data is slower than sorting, parallelizing the CPU work doesn't help.\n\n**Rule of thumb:** If you're not sure, use the standard library's parallel sort. It's been tuned for your platform. Custom parallel quick sort is mainly useful for specific constraints (memory, cache) where the standard isn't optimal.\n\n---\n\n## Summary\n\n### Key Takeaways\n\n- Parallel quick sort exploits independence of recursive subproblems, but the partition step is the bottleneck limiting speedup\n- Unlike merge sort's predictable splits, quick sort's load balance depends entirely on pivot selection\n- Use Fork-Join with median-of-three pivot for production: it handles load imbalance through work stealing\n- For very large arrays (>1M) and high core counts (16+), consider parallel partition or sample sort\n- Expect 3-4x speedup on 8 cores with sequential partition; 5-6x with parallel partition\n- Three-way partition is essential when data has many duplicates\n\n### Complexity Summary\n\n\n| Implementation | Work | Span | Parallelism | Space |\n|----------------|------|------|-------------|-------|\n| Sequential | O(n log n) avg | O(n log n) | 1 | O(log n) |\n| Parallel (seq partition) | O(n log n) avg | O(n) avg | O(log n) | O(log n) |\n| Parallel (parallel partition) | O(n log n) avg | O(log² n) avg | O(n / log n) | O(n) |\n| Sample Sort | O(n log n) | O(n/p + log n) | O(p) | O(n) |\n\n\n### When to Use\n\n- **Fork-Join Quick Sort:** General purpose, memory constrained, moderate parallelism\n- **Parallel Merge Sort:** Need stability, predictable performance, high parallelism\n- **Sample Sort:** Very high core counts (32+), large arrays (100M+)\n- **Three-Way Quick Sort:** Data with many duplicates\n\nFor most applications, use the built-in parallel sort rather than implementing your own.\n\n---\n\n## References\n\n- Intel TBB parallel_sort Documentation - https://www.intel.com/content/www/us/en/docs/onetbb/developer-reference/2021-3/parallel-sort-function.html\n- Java DualPivotQuicksort Source - https://github.com/openjdk/jdk/blob/master/src/java.base/share/classes/java/util/DualPivotQuicksort.java\n- \"Introduction to Algorithms\" by Cormen et al., Chapter 7: Quicksort, Chapter 27: Multithreaded Algorithms\n- \"Parallel Sorting by Regular Sampling\" by Shi and Schaeffer - https://www.cs.odu.edu/~zeil/cs361/s16/Public/parallelSorting/parallelSorting.pdf\n- \"Practical Parallel Sorting\" - Intel Developer Zone\n- \"The Art of Multiprocessor Programming\" by Herlihy and Shavit, Chapter on Work Distribution","pageType":"concurrency-interview"}

Multi-threaded Quick Sort

Ashish Pratap Singh

Get Premium