Quick Sort Algorithm: Partition, Pivot Selection, O(n log n) Average, and Worst-Case (2026)

Published: March 13, 2026 | Category: Dsa | Reading time: ~15 min

Quick Sort is an efficient divide-and-conquer sorting algorithm. It works by selecting a "pivot" element from the array and partitioning the other elements into two groups — those less than the pivot and those greater than the pivot. The pivot is then placed in its correct position, and the algorithm recursively sorts the two subarrays.

This tutorial covers the partition mechanism, pivot selection strategies, average and worst-case complexity analysis, and the reasons Quick Sort is preferred in practice despite its O(n²) worst case.

📖 Table of Contents

Partition Mechanism and Pivot Selection
Complexity Analysis and In-Place Property

Partition Mechanism and Pivot Selection

The most common partitioning scheme is Lomuto partition: choose the last element as pivot, maintain a pointer i for the smaller element, and scan with j. When arr[j] <= pivot, increment i and swap arr[i] and arr[j]. Finally, swap the pivot into position i+1. Hoare partition (choosing the middle element) is faster in practice.

Pivot selection greatly affects performance. Always picking the last element leads to O(n²) on sorted arrays. Random pivot selection, median-of-three, or median-of-medians (introselect) mitigate this. Randomized Quick Sort avoids the worst case with high probability.

// C++ — Lomuto partition
int partition(int arr[], int l, int r) {
  int pivot = arr[r];
  int i = l-1;
  for(int j=l; j= r) return;
  int pi = partition(arr, l, r);
  quickSort(arr, l, pi-1);
  quickSort(arr, pi+1, r);
}

// Java — similar Lomuto partition

// Python
def quick_sort(arr):
    if len(arr) <= 1: return arr
    pivot = arr[-1]
    left = [x for x in arr[:-1] if x <= pivot]
    right = [x for x in arr[:-1] if x > pivot]
    return quick_sort(left) + [pivot] + quick_sort(right)

Complexity Analysis and In-Place Property

Average-case time complexity is O(n log n) with a recurrence of T(n) = T(n/2) + T(n/2) + O(n) when the pivot divides the array evenly. Worst case (sorted array with last-element pivot) is O(n²). Space complexity is O(log n) for the recursion stack in the average case; worst case is O(n) when the recursion is highly unbalanced.

Quick Sort is in-place (it sorts by swapping elements) but is not stable — equal elements can change relative order during partitioning. Despite the O(n²) worst case, Quick Sort is often faster than Merge Sort in practice due to better cache locality and lower constant factors.

// C++ — randomized pivot to avoid worst case
int randomPartition(int arr[], int l, int r) {
  int pi = l + rand() % (r-l+1);
  swap(arr[pi], arr[r]);
  return partition(arr, l, r);
}

// Java — Arrays.sort(int[]) uses Dual-Pivot Quick Sort
// Python — sorted() uses Timsort (not Quick Sort)

// C++ STL uses introsort (Quick Sort + Heap Sort)
sort(arr, arr+n); // introsort

Frequently Asked Questions

What is the worst case for Quick Sort?

When the pivot is always the smallest or largest element (e.g., sorted or reverse-sorted array with Lomuto partition), leading to O(n²) time.

Is Quick Sort stable?

The standard in-place Quick Sort is not stable. Stability can be achieved using an out-of-place partition (like the list-comprehension version in Python), at the cost of extra space.

Originally published on Ayodhyyya. Last updated June 1, 2026.