Why should you care? Sorting is everywhere in software. We sort: Numbers Names Search results Prices Database records Files Scores Logs In the previous article, we learned Merge Sort, which can sort an array in O(n log n) time. Quick Sort also uses the Divide and Conquer strategy, but it approaches the problem differently. Instead of splitting the array simply in half, Quick Sort chooses an element called a pivot and rearranges the array so that: smaller values | pivot | larger values It then recursively sorts the two sides. Quick Sort is particularly important because it is often very fast in practice and is a fundamental sorting algorithm to understand. The Problem Consider: [8, 3, 1, 7, 0, 10, 2] We want: [0, 1, 2, 3, 7, 8, 10] One approach is Merge Sort: Divide → Sort → Merge Quick Sort takes another approach: Choose pivot ↓ Partition ↓ Sort left side ↓ Sort right side For example, choose: pivot = 7 Rearrange the array around it: [3, 1, 0, 2] 7 [8, 10] Now 7 is in its correct final position. We only need to sort: [3, 1, 0, 2] and: [8, 10] This is the central idea behind Quick Sort. The Concept Quick Sort has three main steps: 1. Choose a pivot 2. Partition the array 3. Recursively sort the partitions Step 1: Choose a pivot The pivot can be selected in several ways: First element Last element Middle element Random element Median-based strategy For a simple implementation, we can choose the last element. Step 2: Partition Rearrange the array so that: values < pivot ↓ pivot ↓ values > pivot For example: [6, 3, 8, 5, 2, 7, 4] ↑ pivot After partitioning: [3, 5, 2, 4] [6] [8, 7] The exact arrangement can vary depending on the partition algorithm. The important property is that elements on the left are smaller than the pivot and elements on the right are larger. The pivot is now in its final position. Step 3: Recursively sort Now apply Quick Sort to the two partitions: [3, 5, 2, 4] and: [8, 7] Continue until the partitions contain zero or one element. At that point, they are already sorted. Simple Explanation Imagine organizing students according to height. Choose one student as the reference student. Then ask everyone else to move: Shorter students → left Reference student → middle Taller students → right Now the reference student's relative position is correct. You don't need to move that student again. Then repeat the same process for the shorter group and taller group. Eventually: Shorter group ↓ sorted Reference ↓ Taller group ↓ sorted Together, everything is sorted. That's Quick Sort. Real-world Analogy Imagine arranging books by thickness. Pick one book as the pivot. Place: Thinner books → left Pivot book → middle Thicker books → right Now take the left group and repeat. Then take the right group and repeat. Eventually, every book ends up in the correct order. The key idea is not that the pivot immediately sorts the entire collection. Instead: The pivot divides one large sorting problem into smaller sorting problems. Code Example Let's implement Quick Sort in Java using the Lomuto partition scheme. public static void quickSort( int[] arr, int low, int high) { if (low < high) { int pivotIndex = partition(arr, low, high); quickSort(arr, low, pivotIndex - 1); quickSort(arr, pivotIndex + 1, high); } } Now the partition function: public static int partition( int[] arr, int low, int high) { int pivot = arr[high]; int i = low - 1; for (int j = low; j < high; j++) { if (arr[j] <= pivot) { i++; int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } } int temp = arr[i + 1]; arr[i + 1] = arr[high]; arr[high] = temp; return i + 1; } We can use it like this: public static void main(String[] args) { int[] arr = { 8, 3, 1, 7, 0, 10, 2 }; quickSort(arr, 0, arr.length - 1); for (int value : arr) { System.out.print(value + " "); } } Output: 0 1 2 3 7 8 10 Understanding Partition This is the most important part of Quick Sort. Consider: [4, 2, 7, 3, 1, 6] Suppose: pivot = 6 We want: [values ≤ 6] 6 [values > 6] The partition algorithm scans the array. Whenever it finds a value smaller than or equal to the pivot, it moves that value toward the left partition. Eventually we get something like: [4, 2, 3, 1] 6 [7] The pivot is now correctly positioned. We then recursively sort: [4, 2, 3, 1] and: [7] The right side is already sorted. Why Does Quick Sort Work? The most important observation is: Once the pivot is placed correctly, it never needs to move again. Suppose: [4, 2, 1, 3, 8, 7, 5] Choose: pivot = 5 After partitioning: [4, 2, 1, 3] 5 [8, 7] Everything on the left belongs before 5. Everything on the right belongs after 5. Therefore, the original problem: Sort 7 elements becomes: Sort 4 elements + Sort 2 elements The pivot itself is already finished. This process continues recursively. Time Complexity Quick Sort has different performance depending on how well the pivot divides the array. Best Case If every pivot approximately divides the array in half: n ↓ n/2 + n/2 ↓ n/4 + n/4 + ... There are approximately: log n levels. Each level processes approximately: n elements. Therefore: O(n log n) Average Case With reasonably good pivot selection, Quick Sort has an average complexity of: O(n log n) Worst Case Suppose the array is already sorted: [1, 2, 3, 4, 5, 6, 7] and we always choose the last element as the pivot. Then: pivot = 7 gives: [1, 2, 3, 4, 5, 6] 7 Next: pivot = 6 gives: [1, 2, 3, 4, 5] 6 And so on. Instead of dividing the problem in half, we get: n n - 1 n - 2 n - 3 ... This results in: O(n²) Therefore: Case Time Complexity Best O(n log n) Average O(n log n) Worst O(n²) Space Complexity Quick Sort is often described as an in-place sorting algorithm because it can partition the array without creating another array proportional to n. However, recursion requires stack space. With reasonably balanced partitions: O(log n) stack space is typical. In the worst case, recursion can become: O(n) deep. So: Case Auxiliary Space Average O(log n) Worst O(n) Implementation details and pivot strategy can affect these values. Common Mistakes Mistake 1: Confusing partitioning with sorting Partitioning does not completely sort the array. For example: [3, 1, 4, 2] 5 [8, 7] The left side isn't necessarily sorted: 3, 1, 4, 2 It only satisfies the partition property. We still need to recursively sort both sides. Mistake 2: Forgetting the base case Quick Sort must stop when the partition contains zero or one element. if (low < high) { // partition and recurse } Without this condition, recursion will not terminate correctly. Mistake 3: Creating bad partitions repeatedly Consider: [1, 2, 3, 4, 5, 6, 7] If the pivot is always the largest element: [1, 2, 3, 4, 5, 6] 7 we get highly unbalanced partitions. Repeatedly doing this results in: O(n²) worst-case performance. Pivot selection matters. Mistake 4: Assuming Quick Sort is always O(n log n) Quick Sort is: Average → O(n log n) but: Worst case → O(n²) The quality of the partitions determines the performance. Mistake 5: Forgetting that duplicates matter Consider: [5, 5, 5, 5, 5] Depending on the partition scheme, many equal values can lead to poor partitioning. More sophisticated partition strategies, such as three-way partitioning, can handle many duplicates more efficiently. Advanced Notes 1. Pivot Selection The pivot is one of the most important decisions in Quick Sort. Common approaches include: First element pivot = arr[low] Simple, but potentially bad for sorted data. Last element pivot = arr[high] Also simple, but has the same worst-case issue. Middle element Choosing a middle position can reduce some bad cases, although it does not guarantee good partitions. Random pivot Choose a random element. Randomization makes consistently bad partition patterns much less likely. Median-of-three Choose the median among: first middle last This can provide better pivot choices for certain input patterns. 2. Lomuto vs Hoare Partition The implementation above uses Lomuto partitioning. Another common approach is Hoare partitioning. Lomuto is generally easier to understand. Hoare partitioning can perform fewer swaps and is often more efficient in practice. Understanding both is useful when implementing Quick Sort from scratch. 3. Three-Way Partitioning Suppose: [4, 2, 4, 4, 7, 4, 1] There are many duplicates. Instead of dividing into only two sections: < pivot | ≥ pivot we can create three: < pivot | = pivot | > pivot For pivot 4: [2, 1] | [4, 4, 4, 4] | [7] The equal section requires no further sorting. This can make Quick Sort much more efficient when there are many duplicate values. 4. Quick Sort vs Merge Sort Both are fundamental O(n log n) sorting algorithms on average. Feature Quick Sort Merge Sort Average Time O(n log n) O(n log n) Worst Time O(n²) O(n log n) Typical Auxiliary Space O(log n) O(n) Stable Usually No Yes In-place Usually Yes Usually No Main Operation Partition Merge The biggest conceptual difference is: Merge Sort: Divide → Sort → Merge Quick Sort: Partition → Sort left/right Merge Sort does most of its important work while merging. Quick Sort does most of its important work while partitioning. 5. Why Quick Sort Can Be Fast in Practice Even though Merge Sort has a guaranteed O(n log n) worst-case complexity, Quick Sort can be extremely fast in practice. One reason is that good implementations can operate largely within the original array. That can provide: Good cache behavior Low memory overhead Fewer allocations Efficient in-place partitioning So algorithm analysis tells us the theoretical behavior, while implementation details influence real-world performance. 6. Tail Recursion Optimization A careful Quick Sort implementation can reduce recursion depth by recursively processing the smaller partition first and handling the larger partition iteratively. This can help limit stack usage even when partitions are unbalanced. This is an example of an important engineering principle: Algorithm design and implementation strategy both matter. The Bigger Picture Quick Sort connects several concepts we've already learned. Big-O From the previous article: O(n) O(log n) O(n log n) O(n²) Quick Sort demonstrates why average-case and worst-case analysis matter. Its typical performance is: O(n log n) but poor pivot choices can produce: O(n²) Binary Search Binary Search taught us the power of reducing a problem by eliminating part of the search space. Quick Sort uses a related strategy. Instead of searching: "Which element am I looking for?" we ask: "Which elements belong on each side of the pivot?" Merge Sort Merge Sort and Quick Sort both use: Divide and Conquer but divide the problem differently. Merge Sort: Split by position ↓ Sort ↓ Merge Quick Sort: Choose pivot ↓ Partition by value ↓ Sort partitions This distinction is extremely important. Recursion Quick Sort is another excellent example of recursion. quickSort(left) quickSort(right) Each call works on a smaller part of the original problem. The Most Important Mental Model Don't think: "Quick Sort chooses a random element and sorts around it." Think: "Put one pivot into its final position, then solve the two remaining problems." For example: Before: [8 3 1 7 0 10 2] Choose pivot = 7 ↓ [3 1 0 2] 7 [8 10] ↓ Sort left Sort right ↓ [0 1 2 3] 7 [8 10] ↓ [0 1 2 3 7 8 10] The pivot creates a boundary: everything smaller | pivot | everything larger Once that boundary is correct, the original problem becomes two smaller problems. That's the essence of Quick Sort. Summary Quick Sort is a Divide and Conquer sorting algorithm based on partitioning around a pivot. The process is: Choose Pivot ↓ Partition ↓ Pivot reaches final position ↓ Recursively sort left ↓ Recursively sort right Important points: Quick Sort works by partitioning around a pivot. The pivot ends up in its final position after partitioning. The remaining partitions are sorted recursively. Average time complexity is O(n log n). Worst-case time complexity is O(n²). Good pivot selection helps avoid poor partitions. Quick Sort usually requires less auxiliary memory than Merge Sort. Standard Quick Sort is generally not stable. Three-way partitioning is useful when many duplicate values exist. Quick Sort is one of the most important examples of Divide and Conquer. The central comparison is: Merge Sort ↓ Divide → Sort → Merge Quick Sort ↓ Partition → Sort → Repeat