Quick sort picks a pivot and partitions the array around it.
int partition(vector<int>& a, int lo, int hi) {
int p = a[hi], i = lo - 1;
for (int j = lo; j < hi; j++) if (a[j] < p) swap(a[++i], a[j]);
swap(a[i + 1], a[hi]);
return i + 1;
}
| Case | Time |
|---|---|
| Average | O(n log n) |
| Worst | O(n²) |