Recursive quick sort

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.

Exercise 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).

Show example 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)

Test yourself

Recursive quick sort: match the terms

Base case

lo >= hi
Pivot

Stays in middle
Left

Smaller
Right

Larger
Is quick sort in-place?
- No, extra array needed
- Only with a good pivot
- Only on small arrays
- Yes, only swaps
Show answer

Yes, only swaps — Yes, only swaps
Base case
```
if lo ____hi:
```
Show answer
```
if lo >=hi:
```

Next lesson: Summary - Quick sort

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies