{"title":"Quick Sort","description":"","content":"Quick Sort is one of the most efficient and widely used sorting algorithms in practice. It follows a divide-and-conquer approach, but instead of splitting the array evenly, it selects a pivot and partitions the array into elements smaller and larger than the pivot.\n\nThis partitioning step places the pivot in its correct position, and the same process is then applied recursively to the left and right subarrays. When implemented well, Quick Sort achieves an average time complexity of O(n log n) with excellent performance in real-world scenarios.\n\nHowever, its performance depends on pivot selection, and poor choices can lead to O(n²) time in the worst case.\n\nIn this chapter, you will learn how Quick Sort works step by step, how partitioning is performed, how to choose pivots effectively, and how to implement it efficiently.\n\n---\n\n# What Is Quick Sort?\n\nQuick Sort is a divide-and-conquer sorting algorithm. The core idea revolves around a single operation called **partitioning**.\n\nHere is the strategy in plain English:\n\n1. Pick an element from the array. Call it the **pivot**.\n2. Rearrange the array so that all elements smaller than the pivot are on the left, and all elements greater than the pivot are on the right. The pivot ends up in its correct sorted position.\n3. Recursively apply the same process to the left and right sub-arrays.\n\nThe beauty of this approach is that after the partition step, the pivot is in its final position. It will never move again. Each recursive call places more pivots in their correct positions until the entire array is sorted.\n\n\n```mermaid\nflowchart TD\n A[\"Unsorted Array
[10, 7, 8, 9, 1, 5]\"]:::primary\n B[\"Choose Pivot: 5\"]:::secondary\n C[\"Partition Around 5\"]:::teal\n D[\"Left: [1]
All < 5\"]:::green\n E[\"Pivot: [5]
In correct position\"]:::secondary\n F[\"Right: [7, 8, 9, 10]
All > 5\"]:::red\n G[\"Recursively Sort Left\"]:::primary\n H[\"Recursively Sort Right\"]:::primary\n I[\"Sorted: [1, 5, 7, 8, 9, 10]\"]:::green\n\n A --> B\n B --> C\n C --> D\n C --> E\n C --> F\n D --> G\n F --> H\n G --> I\n H --> I\n\n classDef primary fill:#00ceff,stroke:#000,color:#000\n classDef secondary fill:#ffa94d,stroke:#000,color:#000\n classDef green fill:#69db7c,stroke:#000,color:#000\n classDef red fill:#ff8787,stroke:#000,color:#000\n classDef teal fill:#38d9a9,stroke:#000,color:#000\n```\n\n\nThe diagram above captures the entire algorithm. Pick a pivot, partition, then recurse on each half. That is Quick Sort.\n\nCompare this with Merge Sort, which does the heavy lifting during the merge step (combining two sorted halves). Quick Sort does the heavy lifting during the partition step. By the time you reach the base case (sub-arrays of size 0 or 1), the array is already sorted. There is nothing to combine.\n\n---\n\n# How It Works\n\nLet us break down the algorithm into its key components.\n\n### The Partition Operation\n\nPartitioning is the heart of Quick Sort. There are two classic partition schemes:\n\n**Lomuto Partition Scheme** (simpler, easier to understand):\n\n- Uses the last element as the pivot\n- Maintains a boundary index `i` that tracks where the \"smaller than pivot\" region ends\n- Scans from left to right, swapping elements smaller than the pivot to the front\n- At the end, swaps the pivot into its correct position\n\n**Hoare Partition Scheme** (more efficient):\n\n- Uses the first element as the pivot\n- Uses two pointers starting from opposite ends\n- Pointers move toward each other, swapping elements that are on the wrong side\n- Performs fewer swaps on average (about three times fewer than Lomuto)\n\nWe will focus on Lomuto for the code implementations because it is easier to follow and less error-prone during interviews. Hoare's scheme is more efficient in practice but trickier to implement correctly.\n\n### Step-by-Step Process\n\nHere is the full Quick Sort algorithm using Lomuto partition:\n\n1. If the sub-array has fewer than 2 elements, return (base case)\n2. Select the last element as the pivot\n3. Initialize a boundary index `i` to `low - 1`\n4. Scan elements from `low` to `high - 1`:\n\n- If the current element is less than or equal to the pivot, increment `i` and swap the current element with the element at index `i`\n\n1. After the scan, swap the pivot (at `high`) with the element at `i + 1`\n2. The pivot is now at index `i + 1`, which is its final sorted position\n3. Recursively sort the sub-array to the left of the pivot\n4. Recursively sort the sub-array to the right of the pivot\n\n\n```mermaid\nflowchart TD\n A[\"quickSort(arr, low, high)\"]:::primary\n B{\"low < high?\"}:::secondary\n C[\"pivotIndex = partition(arr, low, high)\"]:::teal\n D[\"quickSort(arr, low, pivotIndex - 1)\"]:::primary\n E[\"quickSort(arr, pivotIndex + 1, high)\"]:::primary\n F[\"Return
(base case)\"]:::green\n\n A --> B\n B -->|Yes| C\n B -->|No| F\n C --> D\n C --> E\n\n classDef primary fill:#00ceff,stroke:#000,color:#000\n classDef secondary fill:#ffa94d,stroke:#000,color:#000\n classDef green fill:#69db7c,stroke:#000,color:#000\n classDef teal fill:#38d9a9,stroke:#000,color:#000\n```\n\n\nThe recursion tree fans out like a binary tree. In the best case (balanced partitions), the tree has log n levels, and each level does O(n) work during partitioning. That gives us O(n log n) total.\n\n---\n\n# Code Implementation\n\n\n```java\npublic class QuickSort {\n\n public static void quickSort(int[] arr, int low, int high) {\n if (low < high) {\n int pivotIndex = partition(arr, low, high);\n quickSort(arr, low, pivotIndex - 1);\n quickSort(arr, pivotIndex + 1, high);\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 int temp = arr[i];\n arr[i] = arr[j];\n arr[j] = temp;\n }\n }\n\n int temp = arr[i + 1];\n arr[i + 1] = arr[high];\n arr[high] = temp;\n\n return i + 1;\n }\n\n public static void main(String[] args) {\n int[] arr = {10, 7, 8, 9, 1, 5};\n quickSort(arr, 0, arr.length - 1);\n System.out.println(java.util.Arrays.toString(arr));\n // Output: [1, 5, 7, 8, 9, 10]\n }\n}\n```\n\n```python\ndef quick_sort(arr, low, high):\n if low < high:\n pivot_index = partition(arr, low, high)\n quick_sort(arr, low, pivot_index - 1)\n quick_sort(arr, pivot_index + 1, high)\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\nif __name__ == \"__main__\":\n arr = [10, 7, 8, 9, 1, 5]\n quick_sort(arr, 0, len(arr) - 1)\n print(arr)\n # Output: [1, 5, 7, 8, 9, 10]\n```\n\n```cpp\n#include \n#include \nusing namespace std;\n\nint partition(vector& 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], arr[j]);\n }\n }\n\n swap(arr[i + 1], arr[high]);\n return i + 1;\n}\n\nvoid quickSort(vector& arr, int low, int high) {\n if (low < high) {\n int pivotIndex = partition(arr, low, high);\n quickSort(arr, low, pivotIndex - 1);\n quickSort(arr, pivotIndex + 1, high);\n }\n}\n\nint main() {\n vector arr = {10, 7, 8, 9, 1, 5};\n quickSort(arr, 0, arr.size() - 1);\n for (int x : arr) cout << x << \" \";\n // Output: 1 5 7 8 9 10\n return 0;\n}\n```\n\n```go\npackage main\n\nimport \"fmt\"\n\nfunc quickSort(arr []int, low int, high int) {\n\tif low < high {\n\t\tpivotIndex := partition(arr, low, high)\n\t\tquickSort(arr, low, pivotIndex-1)\n\t\tquickSort(arr, pivotIndex+1, high)\n\t}\n}\n\nfunc partition(arr []int, low int, 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\nfunc main() {\n\tarr := []int{10, 7, 8, 9, 1, 5}\n\tquickSort(arr, 0, len(arr)-1)\n\tfmt.Println(arr)\n\t// Output: [1, 5, 7, 8, 9, 10]\n}\n```\n\n```csharp\nusing System;\n\npublic class QuickSort\n{\n public static void Sort(int[] arr, int low, int high)\n {\n if (low < high)\n {\n int pivotIndex = Partition(arr, low, high);\n Sort(arr, low, pivotIndex - 1);\n Sort(arr, pivotIndex + 1, high);\n }\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 (arr[i], arr[j]) = (arr[j], arr[i]);\n }\n }\n\n (arr[i + 1], arr[high]) = (arr[high], arr[i + 1]);\n return i + 1;\n }\n\n public static void Main()\n {\n int[] arr = { 10, 7, 8, 9, 1, 5 };\n Sort(arr, 0, arr.Length - 1);\n Console.WriteLine(string.Join(\", \", arr));\n // Output: 1, 5, 7, 8, 9, 10\n }\n}\n```\n\n```rust\npub struct QuickSort;\n\nimpl QuickSort {\n pub fn quick_sort(arr: &mut Vec, low: i32, high: i32) {\n if low < high {\n let pivot_index = Self::partition(arr, low, high);\n Self::quick_sort(arr, low, pivot_index - 1);\n Self::quick_sort(arr, pivot_index + 1, high);\n }\n }\n\n fn partition(arr: &mut Vec, low: i32, high: i32) -> i32 {\n let pivot = arr[high as usize];\n let mut i = low - 1;\n\n for j in low..high {\n if arr[j as usize] <= pivot {\n i += 1;\n arr.swap(i as usize, j as usize);\n }\n }\n\n arr.swap((i + 1) as usize, high as usize);\n i + 1\n }\n}\n\nfn main() {\n let mut arr = vec![10, 7, 8, 9, 1, 5];\n let len = arr.len() as i32;\n QuickSort::quick_sort(&mut arr, 0, len - 1);\n println!(\"{:?}\", arr);\n // Output: [1, 5, 7, 8, 9, 10]\n}\n```\n\n```javascript\nfunction quickSort(arr, low, high) {\n if (low < high) {\n const pivotIndex = partition(arr, low, high);\n quickSort(arr, low, pivotIndex - 1);\n quickSort(arr, pivotIndex + 1, high);\n }\n}\n\nfunction partition(arr, low, high) {\n const pivot = arr[high];\n let i = low - 1;\n\n for (let j = low; j < high; j++) {\n if (arr[j] <= pivot) {\n i++;\n [arr[i], arr[j]] = [arr[j], arr[i]];\n }\n }\n\n [arr[i + 1], arr[high]] = [arr[high], arr[i + 1]];\n return i + 1;\n}\n\nconst arr = [10, 7, 8, 9, 1, 5];\nquickSort(arr, 0, arr.length - 1);\nconsole.log(arr);\n// Output: [1, 5, 7, 8, 9, 10]\n```\n\n```typescript\nfunction quickSort(arr: number[], low: number, high: number): void {\n if (low < high) {\n const pivotIndex = partition(arr, low, high);\n quickSort(arr, low, pivotIndex - 1);\n quickSort(arr, pivotIndex + 1, high);\n }\n}\n\nfunction partition(arr: number[], low: number, high: number): number {\n const pivot = arr[high];\n let i = low - 1;\n\n for (let j = low; j < high; j++) {\n if (arr[j] <= pivot) {\n i++;\n [arr[i], arr[j]] = [arr[j], arr[i]];\n }\n }\n\n [arr[i + 1], arr[high]] = [arr[high], arr[i + 1]];\n return i + 1;\n}\n\nconst arr: number[] = [10, 7, 8, 9, 1, 5];\nquickSort(arr, 0, arr.length - 1);\nconsole.log(arr);\n// Output: [1, 5, 7, 8, 9, 10]\n```\n\n\nThe partition function does the real work: it places the pivot in its correct position and returns that index. The quickSort function handles the recursion.\n\n---\n\n# Example Walkthrough\n\nLet us trace through Quick Sort step by step using the array `[10, 7, 8, 9, 1, 5]`.\n\n### First Call: quickSort(arr, 0, 5)\n\nThe pivot is `arr[5] = 5`. We run the Lomuto partition with `i = -1`.\n\n\n```shell\nInitial: [10, 7, 8, 9, 1, 5] pivot = 5, i = -1\n\nj=0: arr[0]=10 > 5 -> skip i=-1\nj=1: arr[1]=7 > 5 -> skip i=-1\nj=2: arr[2]=8 > 5 -> skip i=-1\nj=3: arr[3]=9 > 5 -> skip i=-1\nj=4: arr[4]=1 <= 5 -> i=0, swap arr[0] and arr[4] i=0\n Array: [1, 7, 8, 9, 10, 5]\n\nSwap pivot into position: swap arr[1] and arr[5]\n Array: [1, 5, 8, 9, 10, 7]\n Pivot index = 1\n```\n\n\nAfter partition, `5` is in its correct sorted position at index 1. Everything to its left (`[1]`) is smaller, and everything to its right (`[8, 9, 10, 7]`) is larger.\n\n### Second Call: quickSort(arr, 0, 0)\n\nThe left sub-array is `[1]`. A single element is already sorted. Base case, return.\n\n### Third Call: quickSort(arr, 2, 5)\n\nThe sub-array is `[8, 9, 10, 7]`. The pivot is `arr[5] = 7`.\n\n\n```shell\nSub-array indices 2-5: [8, 9, 10, 7] pivot = 7, i = 1\n\nj=2: arr[2]=8 > 7 -> skip i=1\nj=3: arr[3]=9 > 7 -> skip i=1\nj=4: arr[4]=10 > 7 -> skip i=1\n\nSwap pivot into position: swap arr[2] and arr[5]\n Array: [1, 5, 7, 9, 10, 8]\n Pivot index = 2\n```\n\n\nNow `7` is in its correct position at index 2.\n\n### Fourth Call: quickSort(arr, 3, 5)\n\nThe sub-array is `[9, 10, 8]`. The pivot is `arr[5] = 8`.\n\n\n```shell\nSub-array indices 3-5: [9, 10, 8] pivot = 8, i = 2\n\nj=3: arr[3]=9 > 8 -> skip i=2\nj=4: arr[4]=10 > 8 -> skip i=2\n\nSwap pivot into position: swap arr[3] and arr[5]\n Array: [1, 5, 7, 8, 10, 9]\n Pivot index = 3\n```\n\n\nNow `8` is at index 3.\n\n### Fifth Call: quickSort(arr, 4, 5)\n\nThe sub-array is `[10, 9]`. The pivot is `arr[5] = 9`.\n\n\n```shell\nSub-array indices 4-5: [10, 9] pivot = 9, i = 3\n\nj=4: arr[4]=10 > 9 -> skip i=3\n\nSwap pivot into position: swap arr[4] and arr[5]\n Array: [1, 5, 7, 8, 9, 10]\n Pivot index = 4\n```\n\n\nBoth remaining sub-arrays (`[]` and `[10]`) are base cases.\n\n**Final sorted array: `[1, 5, 7, 8, 9, 10]`**\n\nNotice how each partition places exactly one element (the pivot) in its final position. After enough partitions, every element has been placed correctly.\n\n\n```mermaid\nflowchart TD\n A[\"[10, 7, 8, 9, 1, 5]
pivot = 5\"]:::primary\n B[\"[1]\"]:::green\n C[\"[5]\"]:::secondary\n D[\"[8, 9, 10, 7]
pivot = 7\"]:::primary\n E[\"[]\"]:::green\n F[\"[7]\"]:::secondary\n G[\"[9, 10, 8]
pivot = 8\"]:::primary\n H[\"[]\"]:::green\n I[\"[8]\"]:::secondary\n J[\"[10, 9]
pivot = 9\"]:::primary\n K[\"[10]\"]:::green\n L[\"[9]\"]:::secondary\n\n A --> B\n A --> C\n A --> D\n D --> E\n D --> F\n D --> G\n G --> H\n G --> I\n G --> J\n J --> K\n J --> L\n\n classDef primary fill:#00ceff,stroke:#000,color:#000\n classDef secondary fill:#ffa94d,stroke:#000,color:#000\n classDef green fill:#69db7c,stroke:#000,color:#000\n```\n\n\nThe diagram shows the recursion tree. Orange nodes are pivots that have been placed in their final positions. Green nodes are base cases. Blue nodes are sub-arrays that still need sorting.\n\n---\n\n# Complexity Analysis\n\n\n| Case | Time Complexity | Space Complexity | Explanation |\n|------|----------------|------------------|-------------|\n| **Best** | O(n log n) | O(log n) | Pivot always splits array into two equal halves |\n| **Average** | O(n log n) | O(log n) | Expected performance with random input |\n| **Worst** | O(n^2) | O(n) | Array is already sorted and pivot is always the smallest or largest |\n\n\n**Stability:** Quick Sort is **not stable**. Equal elements may change their relative order during swaps.\n\n### Why O(n log n) on Average?\n\nEach partition step does O(n) work, scanning through the sub-array once. The key question is: how many levels of recursion are there?\n\nWhen the pivot splits the array roughly in half each time, the recursion depth is log n. Each level does a total of O(n) work across all partitions at that level. So the total work is O(n) * O(log n) = O(n log n).\n\n### Why O(n^2) in the Worst Case?\n\nThe worst case happens when the partition is maximally unbalanced. If the pivot is always the smallest or largest element, one partition gets n-1 elements and the other gets 0 elements. This creates n levels of recursion instead of log n, and each level still does O(n) work. The total becomes O(n) * O(n) = O(n^2).\n\nWhen does this happen? The classic scenario: the array is already sorted (ascending or descending), and you always pick the first or last element as the pivot. Every partition produces the worst possible split.\n\n### Space Complexity\n\nQuick Sort sorts in-place, so it does not allocate extra arrays. However, it uses the call stack for recursion. In the best case, the recursion depth is O(log n). In the worst case, it is O(n), which can cause a stack overflow on very large sorted arrays.\n\n\n```mermaid\nflowchart LR\n subgraph Best[\"Best Case: O(log n) depth\"]\n direction TB\n A1[\"n\"]:::primary\n A2[\"n/2\"]:::primary\n A3[\"n/2\"]:::primary\n A4[\"n/4\"]:::teal\n A5[\"n/4\"]:::teal\n A1 --> A2\n A1 --> A3\n A2 --> A4\n A2 --> A5\n end\n\n subgraph Worst[\"Worst Case: O(n) depth\"]\n direction TB\n B1[\"n\"]:::red\n B2[\"n-1\"]:::red\n B3[\"n-2\"]:::red\n B4[\"n-3\"]:::red\n B1 --> B2\n B2 --> B3\n B3 --> B4\n end\n\n classDef primary fill:#00ceff,stroke:#000,color:#000\n classDef teal fill:#38d9a9,stroke:#000,color:#000\n classDef red fill:#ff8787,stroke:#000,color:#000\n```\n\n\nThe left tree shows balanced partitions (best case), where the depth is log n. The right tree shows unbalanced partitions (worst case), where the depth is n. This visual makes it clear why pivot selection matters so much.\n\n---\n\n# When to Use Quick Sort\n\n### Good Fit\n\n- **General-purpose sorting**: When you need to sort data and have no specific constraints, Quick Sort is a strong default choice\n- **Memory-constrained environments**: Quick Sort works in-place with O(log n) stack space, unlike Merge Sort which needs O(n) extra memory\n- **Cache-friendly workloads**: Since Quick Sort operates on contiguous memory, it benefits from CPU cache locality. This is a major reason it outperforms Merge Sort in practice despite both being O(n log n)\n- **Average case performance matters more than worst case**: If your data is not adversarial and you use randomized pivot selection, the average case dominates\n\n### Not Ideal For\n\n- **Worst case sensitive applications**: If you absolutely cannot tolerate O(n^2) (real-time systems, adversarial inputs), consider Merge Sort or Heap Sort, which guarantee O(n log n)\n- **Stability required**: Quick Sort is not stable. If you need equal elements to preserve their original order, use Merge Sort\n- **Linked lists**: Quick Sort's advantage comes from in-place array operations and cache locality. On linked lists, these advantages vanish. Merge Sort is the better choice for linked lists because it does not need random access\n- **Small arrays**: For very small arrays (less than 10-20 elements), Insertion Sort is faster due to lower overhead. In practice, optimized Quick Sort implementations switch to Insertion Sort for small sub-arrays\n\n### Pivot Selection Strategies\n\nThe pivot strategy is the single most important decision in a Quick Sort implementation. A bad pivot leads to O(n^2). A good pivot keeps things at O(n log n).\n\n**1. Last or First Element (Naive)** Simple but dangerous. Degrades to O(n^2) on sorted or nearly sorted data, which is surprisingly common in real applications.\n\n**2. Random Pivot** Pick a random element and swap it with the last element before partitioning. This makes the worst case extremely unlikely, though not impossible. The expected time complexity is O(n log n) regardless of input order.\n\n**3. Median-of-Three** Pick the median of the first, middle, and last elements. This avoids the worst case on sorted data and performs well in practice. Many production implementations use this strategy.\n\nThe table below summarizes the trade-offs:\n\n\n| Strategy | Worst Case Input | Implementation Effort | Used In Practice |\n|----------|-----------------|----------------------|------------------|\n| First/Last element | Sorted arrays | Trivial | Rarely |\n| Random pivot | Extremely unlikely | Easy | Often |\n| Median-of-three | Very unlikely | Moderate | Standard libraries |\n","pageType":"dsa"}

Quick Sort

Ashish Pratap Singh

Get Premium