Quick Sort and Pivot Selection
Build quick sort with Lomuto and Hoare partition schemes, discuss worst-case O(n²) and how randomised pivot selection mitigates it.
Quick Sort and Pivot Selection is a free DSA Interview Prep lesson on CoddyKit — lesson 3 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the DSA Interview Prep learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.
Quick Sort: In-Place Divide and Conquer
Quick sort is the most widely used sorting algorithm in practice. Unlike merge sort, it sorts in-place without allocating extra arrays. The core idea: choose a pivot element, partition the array so all elements less than the pivot come before it and all greater elements after it, then recursively sort each partition. The partition step takes O(n) time, and with a good pivot, the recursion depth is O(log n).
def quick_sort(arr, lo=0, hi=None):
if hi is None: hi = len(arr) - 1
if lo < hi:
pivot_idx = partition(arr, lo, hi)
quick_sort(arr, lo, pivot_idx - 1) # sort left
quick_sort(arr, pivot_idx + 1, hi) # sort right
def partition(arr, lo, hi):
pivot = arr[hi] # Lomuto: choose last element as pivot
i = lo - 1
for j in range(lo, hi):
if arr[j] <= pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i+1], arr[hi] = arr[hi], arr[i+1]
return i + 1
arr = [3, 6, 8, 10, 1, 2, 1]
quick_sort(arr)
print(arr) # [1, 1, 2, 3, 6, 8, 10]Lomuto Partition Scheme
The Lomuto partition uses the last element as pivot. A slow pointer i tracks the boundary of the 'less than pivot' region; a fast pointer j scans forward. When arr[j] <= pivot, increment i and swap arr[i] with arr[j], extending the small-element region. After the scan, place the pivot at i+1 by swapping with arr[hi]. Simple to implement but performs 3× more swaps than Hoare's scheme.
def lomuto_partition_traced(arr, lo, hi):
pivot = arr[hi]
i = lo - 1
print(f'Pivot: {pivot}, array: {arr[lo:hi+1]}')
for j in range(lo, hi):
if arr[j] <= pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i+1], arr[hi] = arr[hi], arr[i+1]
print(f'After partition: {arr[lo:hi+1]}')
return i + 1
arr = [3, 1, 4, 1, 5, 9, 2, 6]
lomuto_partition_traced(arr, 0, len(arr)-1)Hoare Partition Scheme
The Hoare partition uses two pointers starting at both ends, moving inward until they cross. It chooses the pivot (usually first element) and moves elements smaller than pivot to the left and larger to the right. Hoare's scheme makes 3× fewer swaps than Lomuto and works better with equal elements, but the pivot does not end up at its final position after partitioning — requiring slightly different recursive calls.
def hoare_partition(arr, lo, hi):
pivot = arr[lo] # first element as pivot
i, j = lo - 1, hi + 1
while True:
i += 1
while arr[i] < pivot: i += 1
j -= 1
while arr[j] > pivot: j -= 1
if i >= j: return j
arr[i], arr[j] = arr[j], arr[i]
def quick_sort_hoare(arr, lo=0, hi=None):
if hi is None: hi = len(arr) - 1
if lo < hi:
p = hoare_partition(arr, lo, hi)
quick_sort_hoare(arr, lo, p) # note: p not p-1
quick_sort_hoare(arr, p+1, hi)
arr = [3, 6, 8, 10, 1, 2, 1]
quick_sort_hoare(arr)
print(arr) # [1, 1, 2, 3, 6, 8, 10]Worst Case O(n²): Already Sorted Input
Quick sort's worst case occurs when the pivot is consistently the smallest or largest element in the partition. With Lomuto's last-element pivot on an already-sorted array, the partition always puts 0 elements on the left and n-1 on the right: the recursion tree degenerates into a chain of depth n, giving O(n²) comparisons. This is why pivot selection is critical and why production implementations randomise the pivot.
import sys
sys.setrecursionlimit(5000)
def quick_sort_naive(arr, lo=0, hi=None):
if hi is None: hi = len(arr) - 1
comparisons = [0]
def _qs(lo, hi):
if lo >= hi: return
pivot = arr[hi] # last element pivot
i = lo - 1
for j in range(lo, hi):
comparisons[0] += 1
if arr[j] <= pivot:
i += 1; arr[i], arr[j] = arr[j], arr[i]
arr[i+1], arr[hi] = arr[hi], arr[i+1]
p = i + 1
_qs(lo, p-1); _qs(p+1, hi)
_qs(lo, hi)
return comparisons[0]
import math
n = 100
sorted_arr = list(range(n))
ops = quick_sort_naive(sorted_arr)
print(f'n={n}, ops={ops}, n^2={n**2}') # ops close to n*(n-1)/2Randomised Pivot: O(n log n) Expected
By choosing the pivot uniformly at random (swap a random element with arr[hi] before partitioning), the probability of consistently choosing bad pivots drops exponentially. The expected number of comparisons is 2n ln(n) ≈ 1.39 n log₂(n), giving O(n log n) expected time with overwhelming probability. This is why randomised quick sort is used in practice — it avoids pathological worst cases that an adversary could craft for fixed-pivot strategies.
import random
def quick_sort_random(arr, lo=0, hi=None):
if hi is None: hi = len(arr) - 1
if lo < hi:
# Randomise pivot
rand_i = random.randint(lo, hi)
arr[rand_i], arr[hi] = arr[hi], arr[rand_i]
# Lomuto partition with last element as pivot
pivot = arr[hi]
i = lo - 1
for j in range(lo, hi):
if arr[j] <= pivot:
i += 1; arr[i], arr[j] = arr[j], arr[i]
arr[i+1], arr[hi] = arr[hi], arr[i+1]
p = i + 1
quick_sort_random(arr, lo, p - 1)
quick_sort_random(arr, p + 1, hi)
arr = list(range(100, 0, -1)) # worst case for naive
quick_sort_random(arr)
print(arr[:10]) # [1,2,3,4,5,6,7,8,9,10]Median of Three Pivot
Another pivot strategy: choose the median of the first, middle, and last elements. This avoids worst-case behaviour on sorted or reverse-sorted inputs (the most common adversarial inputs) while avoiding the overhead of random number generation. Many production implementations use median-of-three or ninther (median of three medians) for large arrays and fall back to insertion sort for small subarrays below a threshold of ~10 elements.
def median_of_three(arr, lo, hi):
mid = (lo + hi) // 2
# Sort lo, mid, hi values in place
if arr[lo] > arr[mid]: arr[lo], arr[mid] = arr[mid], arr[lo]
if arr[lo] > arr[hi]: arr[lo], arr[hi] = arr[hi], arr[lo]
if arr[mid] > arr[hi]: arr[mid], arr[hi] = arr[hi], arr[mid]
# Median is now at arr[mid]; swap to arr[hi-1] as pivot
arr[mid], arr[hi] = arr[hi], arr[mid]
return arr[hi] # pivot value
arr = [3, 9, 1]
print(median_of_three(arr, 0, 2), arr) # 3, [1,3,9] (sorted)Dutch National Flag: Three-Way Partition
Standard partitioning places elements less than pivot on the left and greater on the right, but elements equal to pivot are scattered. Three-way partitioning (Dutch national flag) creates three regions: <pivot, ==pivot, >pivot. This is crucial for arrays with many duplicates — where standard quick sort degrades to O(n²) but three-way quick sort gives O(n) for all-same-value inputs.
def three_way_partition(arr, lo, hi):
pivot = arr[lo]
lt = lo # arr[lo..lt-1] < pivot
gt = hi # arr[gt+1..hi] > pivot
i = lo # current
while i <= gt:
if arr[i] < pivot:
arr[lt], arr[i] = arr[i], arr[lt]
lt += 1; i += 1
elif arr[i] > pivot:
arr[i], arr[gt] = arr[gt], arr[i]
gt -= 1 # don't advance i
else:
i += 1
return lt, gt # pivot occupies arr[lt..gt]
arr = [3, 1, 4, 1, 5, 9, 2, 6, 3, 3]
lt, gt = three_way_partition(arr, 0, len(arr)-1)
print(arr, '| pivot region:', lt, 'to', gt)Quickselect: Kth Smallest in O(n)
Quickselect uses the partition step of quick sort to find the kth smallest element in O(n) average time without fully sorting. After partitioning, the pivot is at its final position p. If p == k, return arr[p]. If k < p, recurse on the left partition; if k > p, recurse on the right. On average, each recursion halves the problem: O(n) + O(n/2) + O(n/4) + ... = O(2n) = O(n).
import random
def quickselect(nums, k):
'''Find kth smallest (0-indexed) in O(n) average.'''
def _select(lo, hi):
if lo == hi: return nums[lo]
rand_i = random.randint(lo, hi)
nums[rand_i], nums[hi] = nums[hi], nums[rand_i]
pivot = nums[hi]
i = lo - 1
for j in range(lo, hi):
if nums[j] <= pivot:
i += 1; nums[i], nums[j] = nums[j], nums[i]
p = i + 1
nums[p], nums[hi] = nums[hi], nums[p]
if p == k: return nums[p]
elif k < p: return _select(lo, p - 1)
else: return _select(p + 1, hi)
return _select(0, len(nums) - 1)
print(quickselect([3,2,1,5,6,4], 1)) # 2 (2nd smallest)Quick Sort Space Complexity
Quick sort is called 'in-place' but uses O(log n) average stack space for recursion (one frame per level of the recursion tree). In the worst case this is O(n) stack depth. To guarantee O(log n) worst-case stack space, always recurse on the smaller partition first and use tail-call optimisation for the larger partition. Python's recursion limit makes very deep quick sort recursions risky — worth mentioning in interviews.
def quick_sort_optimised(arr, lo=0, hi=None):
if hi is None: hi = len(arr) - 1
while lo < hi:
p = lomuto_partition_qs(arr, lo, hi)
# Recurse on smaller partition; iterate on larger
if p - lo < hi - p:
quick_sort_optimised(arr, lo, p - 1)
lo = p + 1 # tail-call elimination
else:
quick_sort_optimised(arr, p + 1, hi)
hi = p - 1
def lomuto_partition_qs(arr, lo, hi):
pivot = arr[hi]; i = lo - 1
for j in range(lo, hi):
if arr[j] <= pivot: i += 1; arr[i], arr[j] = arr[j], arr[i]
arr[i+1], arr[hi] = arr[hi], arr[i+1]
return i + 1Comparing Sorting Algorithms
Synthesise your knowledge:
- Quick sort: O(n log n) expected, O(n²) worst, O(log n) space, unstable, fastest in practice for random data
- Merge sort: O(n log n) guaranteed, O(n) space, stable, best for linked lists and external sort
- Heap sort: O(n log n) guaranteed, O(1) space, unstable, slower in practice due to cache misses
- Insertion sort: O(n) best case, ideal for small n or nearly-sorted data
# Python's sorted() uses Timsort:
# - Hybrid: merge sort for large runs, insertion sort for small (< 64 elements)
# - Stable, O(n log n) worst case
# - O(n) best case for sorted/reverse-sorted/nearly-sorted
# - O(n) extra space
import random
arr = random.sample(range(10000), 1000)
sorted_arr = sorted(arr) # Timsort
print(sorted_arr[:5], '...') # first 5 elementsIntrosort: Combining All Three
Introsort (used in C++ STL std::sort) combines quick sort, heap sort, and insertion sort: start with randomised quick sort; if recursion depth exceeds 2 log n (indicating a bad pivot sequence), switch to heap sort to guarantee O(n log n); use insertion sort for subarrays smaller than 16 elements. This gives O(n log n) worst case with quick sort's average-case speed and insertion sort's efficiency for small subarrays.
# Introsort hybrid (simplified)
def introsort(arr, depth_limit=None):
if depth_limit is None:
import math
depth_limit = 2 * int(math.log2(len(arr) + 1)) if arr else 0
if len(arr) <= 16:
# insertion sort for small arrays
for i in range(1, len(arr)):
key = arr[i]; j = i - 1
while j >= 0 and arr[j] > key:
arr[j+1] = arr[j]; j -= 1
arr[j+1] = key
return arr
if depth_limit == 0:
arr.sort() # fall back to heapsort equivalent
return arr
# Otherwise quick sort
pivot = arr[-1]
small = [x for x in arr[:-1] if x <= pivot]
large = [x for x in arr[:-1] if x > pivot]
return introsort(small, depth_limit-1) + [pivot] + introsort(large, depth_limit-1)
print(introsort([5,3,8,1,9,2,7]))Quick Check
Test your understanding of Data Structures & Algorithms — Coding Interview Prep concepts from this lesson.
Lesson Recap
In this lesson you learned: quick sort partitions in-place around a pivot and recurses on each side, achieving O(n log n) expected time with O(log n) stack space — faster in practice than merge sort for random data, the worst case O(n²) occurs on sorted input with a fixed pivot and is avoided by randomised pivot selection or median-of-three, and three-way partitioning handles duplicate elements efficiently, and quickselect extends the partition idea to find the kth smallest element in O(n) average time without full sorting. Next up we explore non-comparison sorts and Python's built-in sort.
Frequently asked questions
Is the “Quick Sort and Pivot Selection” lesson free?
Yes — the full text of “Quick Sort and Pivot Selection” is free to read here on the web, and the DSA Interview Prep course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the DSA Interview Prep course, upgrade to CoddyKit PRO.
What will I learn in “Quick Sort and Pivot Selection”?
Build quick sort with Lomuto and Hoare partition schemes, discuss worst-case O(n²) and how randomised pivot selection mitigates it. You practise DSA Interview Prep with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.
Do I need any experience to start DSA Interview Prep?
No prior experience is required. DSA Interview Prep on CoddyKit is structured for beginners through advanced learners; this is — lesson 3 of 4, so you can start here or from the beginning and move at your own pace.
How long does the “Quick Sort and Pivot Selection” lesson take?
Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.
Can I write and run code in this DSA Interview Prep lesson?
Yes. Every DSA Interview Prep lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.
All lessons in this course
- Bubble Sort and Insertion Sort
- Merge Sort: Divide, Sort, Merge
- Quick Sort and Pivot Selection
- Non-Comparison Sorts and Python's sort()