Quick Sort is one of the fastest sorting algorithms in practice. It selects a pivot, partitions the array so all smaller elements are left of the pivot and all larger elements are right, then recursively sorts both sides. With good pivot selection (median-of-three or random), average performance is O(n log n) with very small constants.
int partition(vector<int>& arr, int low, int high) {
int pivot = arr[high], i = low - 1;
for (int j = low; j < high; j++)
if (arr[j] <= pivot) swap(arr[++i], arr[j]);
swap(arr[i+1], arr[high]);
return i + 1;
}
void quickSort(vector<int>& arr, int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi-1);
quickSort(arr, pi+1, high);
}
}The heart of Quick Sort is the partition step. A pivot is chosen, then elements are rearranged so all elements smaller than the pivot come before it and all larger elements come after. The pivot is now in its final sorted position.
Poor pivot choice causes O(n²) worst-case performance. Choosing the last element is simple but bad on sorted arrays. Randomized pivot or median-of-three selection keeps average performance at O(n log n).
Unlike Merge Sort, Quick Sort sorts in-place using O(log n) stack space for recursion. This cache-friendly behavior is why Quick Sort is often faster in practice despite the same asymptotic complexity.
The worst case O(n²) occurs when the pivot always splits into one empty partition and one of n-1 elements — e.g., sorting an already-sorted array with last-element pivot. Randomization avoids this in practice.
Quick Sort's worst-case time complexity is:
Which pivot strategy avoids Quick Sort's worst case in practice?
Quick Sort is generally preferred over Merge Sort for in-memory sorting because: