Quick sort

How it works

1. Choose a pivot (here, the first item; other versions use the last, middle or a random item).

2. Partition: put items less than the pivot in a left sub-list and items greater than (or equal to) it in a right sub-list. The pivot is now in its final position between them.

3. Recursively quick sort the left and right sub-lists.

4. A sub-list of zero or one items is sorted (base case).

Trace

Sort [7, 2, 9, 4, 1, 8, 5], pivot = first item.

Result: [1, 2, 4, 5, 7, 8, 9]

Recursive code

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

In-place versions swap items within the list using two pointers moving inwards, which avoids extra lists.

Efficiency

• Best and average case: O(n log n): the pivot splits the list roughly in half each time.
• Worst case: O(n²): the pivot is always the smallest or largest item (for example, first-item pivot on an already sorted list), so each partition removes only one item.

Benefits: very fast in practice; in-place versions need little extra memory. Drawbacks: O(n²) worst case; not stable in its usual in-place form; recursion depth can be large. Choosing a random or median-of-three pivot makes the worst case unlikely.

Worked example

Partition [7, 2, 9, 4, 1, 8, 5] using the first item as the pivot.

1. Pivot = 7.
2. Less than 7, in order: [2, 4, 1, 5].
3. Greater: [9, 8].

Answer: [2, 4, 1, 5] + [7] + [9, 8]

Check yourself

1. Partition [5, 8, 1, 9, 3, 6, 2] using the first item as the pivot. Give the 'less than' sub-list, in its original order, separated by commas.
   Show answer

   1, 3, 2. Items below 5 in order: [1, 3, 2].

2. For the same partition of [5, 8, 1, 9, 3, 6, 2], how many items are in the 'greater than' sub-list?
   Show answer

   3. [8, 9, 6].

3. Quick sort with first-item pivots is applied to [7, 2, 9, 4, 1, 8, 5]. After the first partition, what pivot is chosen for the left sub-list?
   Show answer

   2. Left sub-list [2, 4, 1, 5]; its first item is 2.

4. How many partitions (pivot choices) does quick sort make in total when sorting [7, 2, 9, 4, 1, 8, 5] with first-item pivots? Count every sub-list of two or more items.
   Show answer

   4. Pivots chosen: [7, 2, 4, 9].

5. When does quick sort with a first-item pivot perform worst?
   • When the list is in random order
   • When all items are different
   • When the list has an even length
   • When the list is already sorted
   Show answer

   When the list is already sorted. The pivot is always the smallest, so one side is empty every time.

6. What is the average-case time complexity of quick sort?
   • O(n²)
   • O(n log n)
   • O(log n)
   • O(1)
   Show answer

   O(n log n). Balanced partitions give log n levels of n work.

7. What is true of the pivot after a partition?
   • It is at the start of the list
   • It has been removed from the list
   • It is swapped with the last item
   • It is in its final sorted position
   Show answer

   It is in its final sorted position. Everything smaller is left of it and everything larger is right of it.

Practise with instant feedback Print this lesson

Sources

• Pearson Edexcel International Advanced Subsidiary and Advanced Level in Computer Science specification (2026), Issue 1
• Pearson Edexcel IAL Computer Science sample assessment materials (Unit 3 paper, resource booklet and mark scheme)

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