Implementing a recursive quick sort

The idea

• Base case: 0 or 1 items.
• Choose a pivot: often the first or last item (or the middle item, or a random one).
• Partition: items less than the pivot go to its left, greater to its right. The pivot is now in its final position.
• Recurse on the two parts. No merge step is needed: the parts are already in the right order relative to each other.

A clear version with list comprehensions

This version builds new lists. It is short and easy to check, which suits an exam where correctness matters most.

def quick_sort(items):
    if len(items) <= 1:
        return items
    pivot = items[0]
    smaller = [x for x in items[1:] if x < pivot]
    equal = [x for x in items if x == pivot]
    larger = [x for x in items[1:] if x > pivot]
    return quick_sort(smaller) + equal + quick_sort(larger)

print(quick_sort([33, 10, 55, 71, 29, 3, 18, 42]))

Output:

[3, 10, 18, 29, 33, 42, 55, 71]

An in-place version

Partitioning in place swaps items within one list and uses no extra lists. This is the Lomuto scheme with the last item as pivot:

def partition(a, low, high):
    pivot = a[high]                     # last item as pivot
    i = low - 1                         # end of the 'smaller or equal' region
    for j in range(low, high):
        if a[j] <= pivot:
            i = i + 1
            a[i], a[j] = a[j], a[i]
    a[i + 1], a[high] = a[high], a[i + 1]
    return i + 1                        # final position of the pivot

def quick_sort_in_place(a, low, high):
    if low < high:
        p = partition(a, low, high)
        quick_sort_in_place(a, low, p - 1)
        quick_sort_in_place(a, p + 1, high)

data = [33, 10, 55, 71, 29, 3, 18, 42]
p = partition(data, 0, len(data) - 1)
print(p, data)
quick_sort_in_place(data, 0, len(data) - 1)
print(data)

Output:

5 [33, 10, 29, 3, 18, 42, 55, 71]
[3, 10, 18, 29, 33, 42, 55, 71]

After the first partition, 42 is at index 5: everything to its left is smaller and everything to its right is larger.

Properties

Worked example

Use the list-comprehension version to show the first partition of [5, 9, 2, 7, 1, 5].

1. pivot = 5 (the first item).
2. smaller = items after the first that are < 5: [2, 1].
3. equal = every 5 in the list: [5, 5]. larger = [9, 7].
4. Recursing on [2, 1] and [9, 7] gives [1, 2, 5, 5, 7, 9].

Answer: Collecting all items equal to the pivot in one list handles duplicates safely.

Check yourself

1. What does this program print? ```python def quick_sort(items): if len(items) <= 1: return items pivot = items[0] smaller = [x for x in items[1:] if x < pivot] equal = [x for x in items if x == pivot] larger = [x for x in items[1:] if x > pivot] return quick_sort(smaller) + equal + quick_sort(larger) items = [6, 3, 8, 1, 9, 2] pivot = items[0] print([x for x in items[1:] if x < pivot], [x for x in items[1:] if x > pivot]) ```
   Show answer

   [3, 1, 2] [8, 9]. With pivot 6, the smaller items in their original order are 3, 1, 2 and the larger are 8, 9. Output: `[3, 1, 2] [8, 9]`

2. partition is the function from the lesson. What does this print? ```python def partition(a, low, high): pivot = a[high] # last item as pivot i = low - 1 # end of the 'smaller or equal' region for j in range(low, high): if a[j] <= pivot: i = i + 1 a[i], a[j] = a[j], a[i] a[i + 1], a[high] = a[high], a[i + 1] return i + 1 # final position of the pivot def quick_sort_in_place(a, low, high): if low < high: p = partition(a, low, high) quick_sort_in_place(a, low, p - 1) quick_sort_in_place(a, p + 1, high) a = [7, 2, 9, 4, 5] p = partition(a, 0, 4) print(p, a) ```
   Show answer

   2 [2, 4, 5, 7, 9]. Pivot 5 (the last item). 2 and 4 are swapped into the front region, then 5 is swapped into index 2. Output: `2 [2, 4, 5, 7, 9]`

3. This version records the deepest level of recursion. What does it print? ```python def quick_sort(items, depth=1): global deepest deepest = max(deepest, depth) if len(items) <= 1: return items pivot = items[0] smaller = [x for x in items[1:] if x < pivot] equal = [x for x in items if x == pivot] larger = [x for x in items[1:] if x > pivot] return quick_sort(smaller, depth + 1) + equal + quick_sort(larger, depth + 1) deepest = 0 quick_sort([1, 2, 3, 4, 5, 6]) print(deepest) ```
   Show answer

   6. With sorted input and the first item as pivot, every partition has nothing smaller, so each call removes only one item: `6` levels of calls for 6 items. This is the O(n²) worst case.

4. quick_sort is the function from the lesson. What does this print? ```python def quick_sort(items): if len(items) <= 1: return items pivot = items[0] smaller = [x for x in items[1:] if x < pivot] equal = [x for x in items if x == pivot] larger = [x for x in items[1:] if x > pivot] return quick_sort(smaller) + equal + quick_sort(larger) print(quick_sort([4, 1, 4, 2, 4])) ```
   Show answer

   [1, 2, 4, 4, 4]. All three 4s are collected in the equal list at the first call, so duplicates are kept. Output: `[1, 2, 4, 4, 4]`

5. When does quick sort using the first item as the pivot perform worst?
   • When the list is in random order
   • When all items are different
   • When the list has an even number of items
   • When the list is already sorted, because every partition is as unbalanced as possible
   Show answer

   When the list is already sorted, because every partition is as unbalanced as possible. The pivot is always the smallest item, so each partition removes just one item, giving O(n²).

6. Which statement correctly compares quick sort with merge sort?
   • Quick sort is always O(n log n); merge sort can be O(n²)
   • Quick sort can sort in place with little extra memory, but merge sort guarantees O(n log n) even in the worst case
   • Merge sort sorts in place; quick sort needs extra lists
   • Merge sort has a worst case of O(n²) and quick sort does not
   Show answer

   Quick sort can sort in place with little extra memory, but merge sort guarantees O(n log n) even in the worst case. In-place partitioning saves memory, but a bad pivot can make quick sort O(n²); merge sort is O(n log n) always but needs O(n) extra space.

7. After one partition step, what is true of the pivot?
   • It is at index 0
   • It has been removed from the list
   • It is at the middle index
   • It is in its final sorted position
   Show answer

   It is in its final sorted position. Everything smaller is to its left and everything larger to its right, so it never needs to move again.

Practise with instant feedback Print this lesson

Sources

• Pearson Edexcel International Advanced Subsidiary/Advanced Level in Computer Science specification, Issue 1 (March 2026)
• Pearson Edexcel IAL Computer Science Unit 4 Programming Language Subset (PLS)
• Pearson Edexcel IAL Computer Science sample assessment materials (Unit 3 and Unit 4)

Last updated 8 November 2026. Spotted a mistake? Tell us.