Recursive quick sort
- Algorithms course
- Intermediate
- Lesson 7/80
- 4 min
Recursively sort both sides; O(n log n) average.
Recursive quick sort
After partitioning, quick sort recursively sorts the left and right subarrays around the pivot. The pivot is now in its final position and never moves again.
Base case: if the subarray has one element (lo >= hi) it is sorted. Each call does one partition + two recursive calls.
With a good pivot each level halves the problem; depth log n, total O(n log n). A bad pivot gives O(n^2).
In-place sorting
Quick sort works in-place: no extra array is created, only swaps rearrange the array. Memory is O(log n) (recursion stack).
This is an advantage over merge sort's O(n) extra memory. But it is not stable: equal elements may be reordered.
In practice, on small subarrays (e.g. below 10 elements) we switch to insertion sort; this improves performance.
Practice Recursive quick sort
Write quick_sort(arr, lo, hi). If lo >= hi return; else partition and recurse on both sides. Print [1, 2, 5, 8, 9] with arr=[5,2,8,1,9]; quick_sort(arr,0,4); print(arr).
Starter code
def quick_sort(arr, lo, hi):
# Partition and recurseSample solution
def partition(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 + 1
def quick_sort(arr, lo, hi):
# Partition and recurse
if lo >= hi:
return
p = partition(arr, lo, hi)
quick_sort(arr, lo, p - 1)
quick_sort(arr, p + 1, hi)
arr = [5, 2, 8, 1, 9]
quick_sort(arr, 0, 4)
print(arr)Expected output
[1, 2, 5, 8, 9]
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 Recursive quick sort: match the terms
| Term | Meaning |
|---|---|
Base case |
lo >= hi |
Pivot |
Stays in middle |
Left |
Smaller |
Right |
Larger |
2 Is quick sort in-place?
- No, extra array needed
- Only with a good pivot
- Only on small arrays
- Yes, only swaps Correct answer
Explanation: Yes, only swaps
3 Base case
if lo ____hi:if lo >=hi:Explanation: >= is right.