Quick Sort Algorithm & Complexities

Algorithm (Lomuto / Hoare partition)

QuickSort(A, low, high):
  if low < high:
    p = Partition(A, low, high)  // pivot = A[high] (Lomuto)
    QuickSort(A, low, p-1)
    QuickSort(A, p+1, high)

Partition(A, low, high):
  pivot = A[high]; i = low-1
  for j=low to high-1:
    if A[j] <= pivot:
      i++; swap A[i], A[j]
  swap A[i+1], A[high]; return i+1

Hoare partition uses two pointers from both ends, fewer swaps on duplicates.

Example with [5,2,9,3,7]

Pivot 7 → partition → [5,2,3,7,9] → recurse left [5,2,3] pivot3→[2,3,5] + right [9].

Time Complexity

Recurrence $T(n)=T(k)+T(n-k-1)+\Theta(n)$ where $k$ = size of left part.

• Best case: balanced partition $k\approx n/2$ each level → $T(n)=2T(n/2)+\Theta(n)$ → $\Theta(n\log n)$ (also when all elements distinct and pivot median).
• Average case: over random permutation / random pivot — expected balanced → $\Theta(n\log n)$ expected (proof via linearity of expectation, harmonic sum).
• Worst case: already sorted + pivot = last element → $k=0$ or $n-1$ → $T(n)=T(n-1)+\Theta(n)$ → $\Theta(n^2)$ (e.g., sorted [1,2,3,4,5]).

Space: $O(\log n)$ stack average/best, $O(n)$ worst (if tail recursion not optimized); in-place partitioning $O(1)$ auxiliary.

Why average is good

Randomized QuickSort (random pivot) expected $O(n\log n)$ regardless of input; practical fastest due to low constants and cache locality.