Quick Sort
Picks a pivot, moves smaller values to its left and larger ones to its right, then sorts each side the same way.
How it works
Quick sort is a divide and conquer algorithm, like merge sort, but it does its work before splitting instead of after. It picks one value as the pivot and partitions the range around it:
- The last value in the range is the pivot.
- A boundary
istarts at the left edge. Every value to its left is smaller than the pivot. - A pointer
jwalks the range. Wheneverarray[j]is smaller than the pivot, it is swapped to the boundary and the boundary moves one step right. - Finally the pivot is swapped into the boundary. It is now in its final position: everything left of it is smaller, everything right of it is not.
Quick sort then calls itself on the left part and the right part. A range of zero or one value is already sorted, so the recursion stops there.
This scheme is called the Lomuto partition. It is the simplest to follow; Hoare's original scheme does fewer swaps.
When to use it
Quick sort is usually the fastest comparison sort in practice: it sorts in place, its inner loop is tiny and it reads memory in order. It is the base of introsort, used by C++'s std::sort. Its weak spot is the pivot: always taking the last value turns already sorted input into the O(n²) worst case, so real implementations pick a random pivot or the median of three values. It is not stable.
Complexity
It is not stable: partitioning swaps values across long distances, so equal values can change order.
| Case | Time | When |
|---|---|---|
| Best | O(n log n) | Every pivot splits its range into two equal halves |
| Average | O(n log n) | Random order |
| Worst | O(n²) | Already sorted (or reversed): every pivot is the min or max |
| Extra space | Why |
|---|---|
| O(log n) | It sorts in place; the extra space is the recursion stack (O(n) in the worst case) |
Implementations
function quickSort(array, lo = 0, hi = array.length - 1) {
if (lo >= hi) return array;
const pivot = array[hi];
let i = lo;
for (let j = lo; j < hi; j++) {
if (array[j] < pivot) {
[array[i], array[j]] = [array[j], array[i]];
i++;
}
}
[array[i], array[hi]] = [array[hi], array[i]];
quickSort(array, lo, i - 1);
quickSort(array, i + 1, hi);
return array;
}
def quick_sort(array):
a = list(array)
def sort(lo, hi):
if lo >= hi:
return
pivot = a[hi]
i = lo
for j in range(lo, hi):
if a[j] < pivot:
a[i], a[j] = a[j], a[i]
i += 1
a[i], a[hi] = a[hi], a[i]
sort(lo, i - 1)
sort(i + 1, hi)
sort(0, len(a) - 1)
return a
#include <utility>
#include <vector>
void sort(std::vector<int>& a, int lo, int hi) {
if (lo >= hi) return;
const int pivot = a[hi];
int i = lo;
for (int j = lo; j < hi; j++) {
if (a[j] < pivot) std::swap(a[i++], a[j]);
}
std::swap(a[i], a[hi]);
sort(a, lo, i - 1);
sort(a, i + 1, hi);
}
std::vector<int> quickSort(std::vector<int> a) {
sort(a, 0, static_cast<int>(a.size()) - 1);
return a;
}