Explain quick sort pivot choice and average vs worst case.

Quick sort

Pick pivot, partition smaller/larger, recurse—O(n log n) average, O(n²) worst (bad pivot). In-place, cache-friendly; often faster than merge in practice.

• Pivot: random or median-of-three reduces worst case risk.
• Not stable by default.
• Worst case when already sorted with naive pivot—use introsort hybrids.

int partition(int[] a, int lo, int hi) {
  int pivot = a[hi], i = lo - 1;
  for (int j = lo; j < hi; j++) if (a[j] <= pivot) swap(a, ++i, j);
  swap(a, i + 1, hi);
  return i + 1;
}