Quick Sort
Overview
Quick Sort is another Divide and Conquer algorithm, but it takes the opposite approach of Merge Sort. Instead of doing the heavy lifting during the 'merge', Quick Sort does the heavy lifting during the 'divide'.
It works by selecting a Pivot element from the array. It then 'Partitions' the array: it physically moves every element smaller than the pivot to the left of the pivot, and every element larger to the right. Once partitioned, the pivot is guaranteed to be in its absolute final sorted position! It then recursively applies this process to the left and right sub-arrays.
Quick Sort is highly prized because it operates In-Place (O(1) auxiliary array space, though O(log N) stack space) and has incredible cache-locality, making it faster than Merge Sort in practical, real-world benchmarks. However, if poorly implemented, its worst-case time complexity degrades to a catastrophic O(N^2).
Syntax
public class QuickSort {
public static void sort(int[] arr, int left, int right) {
if (left < right) {
// Partition the array and get the pivot's final sorted index
int pivotIndex = partition(arr, left, right);
// Recursively sort the left and right sides
sort(arr, left, pivotIndex - 1);
sort(arr, pivotIndex + 1, right);
}
}
// Lomuto Partition Scheme
private static int partition(int[] arr, int left, int right) {
// Choose the last element as the pivot
int pivot = arr[right];
int i = left - 1; // Index of smaller element
for (int j = left; j < right; j++) {
// If current element is smaller than the pivot
if (arr[j] < pivot) {
i++;
// Swap arr[i] and arr[j]
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// Finally, swap the pivot into its correct place (i + 1)
int temp = arr[i + 1];
arr[i + 1] = arr[right];
arr[right] = temp;
return i + 1; // Return the pivot's new permanent index
}
}Common Pitfalls
- The O(N^2) Worst-Case Nightmare. If you always pick the last element as the pivot, and the array is already sorted, Quick Sort won't divide the array in half. It will peel off exactly one element per recursive call. This causes O(N) recursive depth and O(N) scanning per level, resulting in O(N^2) time and StackOverflow crashes.
- Failing to randomize the pivot. To prevent the O(N^2) worst-case from being triggered by malicious input or sorted data, modern implementations pick a random element as the pivot, or use the 'Median of Three' method.
- Instability. Unlike Merge Sort, Quick Sort is NOT stable. The heavy swapping during the partition phase will scramble the relative order of duplicate elements.
Interview Questions
Two reasons: Memory and Cache Locality. Quick Sort sorts 'In-Place', saving massive amounts of RAM (no O(N) temp arrays). Furthermore, because it sequentially scans and swaps elements directly in a single contiguous array block, it works perfectly with modern CPU L1/L2 caches, resulting in raw execution speeds far faster than Merge Sort.
QuickSelect is a modification of Quick Sort used to find the Kth smallest/largest element in an array in O(N) time. Instead of recursively sorting both sides of the pivot, you check the pivot's final index. If it is K, you are done! If K is smaller, you only recurse on the left half. It throws away half the array at each step.
Real-World Example
Java's default Arrays.sort(primitiveArray) uses Dual-Pivot QuickSort. Instead of choosing one pivot and splitting the array into two zones (less than, greater than), it chooses two pivots and splits the array into three zones. This mathematically reduces the depth of recursion and speeds up processing significantly.
// Under the hood in java.util.Arrays (simplified concept)
public static void sort(int[] a) {
DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
}Check Your Knowledge
Test your understanding of Quick Sort with these quick questions.