Quick Sort Explained

Pick a pivot element. Partition the array so that everything smaller than the pivot ends up to its left and everything larger to its right — now the pivot is in its final position. Then recursively apply the same process to the left and right partitions. When the partitions shrink to size one, the array is sorted.

quickSort(a, lo, hi):
  if lo < hi:
    p = partition(a, lo, hi)
    quickSort(a, lo, p-1)
    quickSort(a, p+1, hi)

partition(a, lo, hi):
  pivot = a[hi]
  i = lo - 1
  for j from lo to hi-1:
    if a[j] < pivot:
      i++; swap(a[i], a[j])
  swap(a[i+1], a[hi])
  return i+1

Quick Sort averages O(n log n) but degrades to O(n²) when the pivot is consistently the smallest or largest element — which naive 'always pick the last element' does on sorted input. The fixes are randomized pivots or median-of-three (pivot = median of first, middle, last). These make the worst case astronomically unlikely. It is in-place (O(log n) stack) but not stable.

Both are O(n log n), but Quick Sort sorts in-place with contiguous memory access, so it stays in CPU cache and avoids the allocation overhead of Merge Sort. That is why it is typically 2-3x faster on arrays that fit in memory. Read the full analysis in Why Quick Sort is faster than Merge Sort.