Quick Sort
Learn how quick sort partitions around a pivot to sort in-place with average O(n log n) time.
Quick Sort
Quick sort picks a pivot element and partitions the array so everything smaller than the pivot goes left, everything larger goes right. The pivot is now in its final sorted position. Recursively sort the left and right partitions. No merging needed — the sorting happens in-place during partitioning.
How it works
def quick_sort(arr, low=0, high=None):
if high is None:
high = len(arr) - 1
if low < high:
pivot_idx = partition(arr, low, high)
quick_sort(arr, low, pivot_idx - 1)
quick_sort(arr, pivot_idx + 1, high)
return arr
def partition(arr, low, high):
pivot = arr[high] # choose last element as pivot
i = low - 1 # index of smaller element
for j in range(low, high):
if arr[j] <= pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
# place pivot in its correct position
arr[i + 1], arr[high] = arr[high], arr[i + 1]
return i + 1How the partition works
Partition [3, 6, 8, 10, 1, 2, 1], pivot = 1 (last element)
i = -1
j=0: arr[0]=3 > 1 — skip
j=1: arr[1]=6 > 1 — skip
j=2: arr[2]=8 > 1 — skip
j=3: arr[3]=10 > 1 — skip
j=4: arr[4]=1 ≤ 1 — i=0, swap arr[0] and arr[4]: [1, 6, 8, 10, 3, 2, 1]
j=5: arr[5]=2 > 1 — skip
Place pivot: swap arr[i+1]=arr[1] and arr[high]=arr[6]: [1, 1, 8, 10, 3, 2, 6]
pivot is now at index 1 — everything left is ≤ 1, everything right is > 1Pivot selection matters
The pivot choice dramatically affects performance:
Last element (shown above) — simple, but O(n²) on already-sorted arrays. Every partition produces one empty subarray and one of size n-1 — n levels deep instead of log n.
Random pivot — pick a random element as pivot. O(n²) becomes extremely unlikely. The expected case is O(n log n).
Median-of-three — take the median of the first, middle, and last elements. Avoids sorted-array worst case with minimal overhead.
def partition_random(arr, low, high):
import random
rand_idx = random.randint(low, high)
arr[rand_idx], arr[high] = arr[high], arr[rand_idx]
return partition(arr, low, high)Quick sort is often faster than merge sort in practice despite the same O(n log n) average — it has better cache locality (in-place) and lower constant factors. Python's sorted() uses Timsort, but most C++ and Java standard library sorts use quicksort variants (introsort) for in-place sorting.
Quick sort vs merge sort
| Quick sort | Merge sort | |
|---|---|---|
| Time (average) | O(n log n) | O(n log n) |
| Time (worst) | O(n²) | O(n log n) |
| Space | O(log n) call stack | O(n) |
| In-place | Yes | No |
| Stable | No | Yes |
| Pivot dependent | Yes | No |
Complexity
| Case | Time | Space |
|---|---|---|
| Best | O(n log n) | O(log n) |
| Average | O(n log n) | O(log n) |
| Worst (sorted input, bad pivot) | O(n²) | O(n) |