← VCE Software Development U3O1

Quick sort in Python

Recursive step of quick sort: sorts the smaller and larger lists by calling itself, then joins them around the equal items. Base case len(items) <= 1 stops it.

Part of: VCE Software Development - U3O1 - Programming — Module 153

Understanding Quick sort in Python in VCE Software Development U3O1

What it does: This list comprehension collects every item that is less than the pivot into the smaller list. A list with 0 or 1 items is already sorted, so it is returned as is. Using >= 1 would return almost every list unsorted, and the recursion would never happen properly. Smaller values must come first for an ascending sort, then the equal items, then the larger values. Sorted input is a useful edge case. The function should return the same order, and it checks that the smaller and larger lists are built correctly. This base case stops quick_sort calling itself forever, because a list of 0 or 1 items needs no sorting.

Common mistakes: The base case must stop on lists of length 0 or 1, so it should be len(items) <= 1. With >= 1, every non-empty list is returned unsorted, and an empty list would crash at items[0]. Items smaller than the pivot belong in the smaller list, so this should be smaller.append(x). Putting them in larger leaves the smaller list empty and the sort is wrong.

Class: _____________________  ·  Name: _____________________  ·  Date: _________

Free printable worksheet with full answer key — or add this module to a class and your students practise it interactively.

🖨 Print worksheet + answer key Add Quick sort in Python to a class →

This module's key terms are also in a printable crossword (Modules 142–155) and word search (Modules 142–166).

Take this worksheet further — free with Cloodit

Each concept is reinforced from every angle — learned, then applied, then tested.

Learning
Duo
Which base case correctly stops quick_sort(items) from recursing forever?
if len(items) <= 1: return itemsif len(items) >= 1: return items
Matches
if len(items) == 5: return items
↓
The base case tests for the wrong length. It should be len(items) <= 1, otherwise short lists never stop and the recursion goes on until it crashes.
Applying
Meanings
Term
return quick_sort(smaller) + equal + quick_sort(larger)
Meaning
Recursive step of quick sort: sorts the smaller and larger lists by calling itself, then joins them around the equal items. Base case len(items) <= 1 stops it.
Practice
def quick_sort(items):
Testing
Gaps
if len(items) 1:
Check Answer
Spots
1def quick_sort(items):
2 if len(items) >= 1:

Cloodit turns curriculum-aligned coding content into journeys students work through one biome at a time.

The 'Camel' badge — Endurance Champion, one of Cloodit's 106 collectible badges
Students earn collectable badges

Over 100 of them, across seven natural biomes.

Study Buddy
Students build a real study resource

Turns their work into revision material ready for Flash Cards and Exam study.

Diamond Dash — one of Cloodit's live, competitive Sprint games
Students lock in with Sprints

Live, competitive practice for the start of the lesson or a teacher-led lesson finisher.

A Cloodit certificate of achievement, ready to personalise and print
Custom printable certificates

Honour your top performers, or encourage a student who's trying hard — ready to print in seconds.

Add to class →

Quick Questions

1. Which base case correctly stops quick_sort(items) from recursing forever?
A. if len(items) >= 1: return items
B. if len(items) <= 1: return items ✓
A list with 0 or 1 items is already sorted, so it is returned as is. Using >= 1 would return almost every list unsorted, and the recursion would never happen properly.
2. Which return line joins the sorted parts in the correct order?
A. return quick_sort(larger) + equal + quick_sort(smaller)
B. return quick_sort(smaller) + equal + quick_sort(larger) ✓
Smaller values must come first for an ascending sort, then the equal items, then the larger values.
3. Given pivot = 5 and items = [7, 2, 5, 9, 1], which list should smaller hold?
A. [2, 1] ✓
B. [2, 5, 1]
smaller holds only values less than the pivot. The 5 matches the pivot, so it belongs in the equal list.
4. Which line builds the larger list correctly?
A. larger = [x for x in items if x > pivot] ✓
B. larger = [x for x in items if x >= pivot]
Using >= would also put the pivot value (and its duplicates) into larger, so they would be sorted again and the list could recurse forever.
5. Why does quick_sort keep an equal list as well as smaller and larger?
A. So duplicates of the pivot are kept and not sorted again ✓
B. So the pivot can be deleted from the sorted result
The equal list holds every item that matches the pivot. This keeps duplicates in the result and stops them being passed into the recursive calls.

Match the Pairs

if len(items) <= 1: return items → The base case: a list with 0 or 1 items is already sorted, so it is returned and the recursion stops.
return quick_sort(smaller) + equal + quick_sort(larger) → The recursive step: sort the smaller and larger lists, then join them around the equal items.
Build the smaller list by keeping only the items less than the pivot → smaller = [x for x in items if x < pivot]
Keep duplicates of the pivot in an equal list so they are not lost or sorted again → equal = [x for x in items if x == pivot]
if len(items) == 5: return items → The base case tests for the wrong length. It should be len(items) <= 1, otherwise short lists never stop and the recursion goes on until it crashes.
return quick_sort(smaller) + quick_sort(larger) → The equal list is missing, so the pivot and any duplicates of it are dropped from the result.

Key Term

return quick_sort(smaller) + equal + quick_sort(larger)
Recursive step of quick sort: sorts the smaller and larger lists by calling itself, then joins them around the equal items. Base case len(items) <= 1 stops it.

Fill in the Blanks

1. if len(items) <= 1: return items
Hint: Type the comparison operator that makes the base case true for lists of length 0 or 1
2. smaller = [x for x in items if x < pivot]
Hint: Type the operator that keeps only items less than the pivot
3. larger = [x for x in items if x > pivot]
Hint: Type the operator that keeps only items greater than the pivot
4. equal = [x for x in items if x == pivot]
Hint: Type the operator that tests for equality, so duplicates of the pivot are kept together
5. return (quick_sort(smaller) + equal + quick_sort(larger))
Hint: Type the name of the function that calls itself to sort the smaller list

Spot the Error

Question 1
A def quick_sort(items):
B if len(items) >= 1:
C return items
D pivot = items[0]
E smaller = []
Line B — The base case must stop on lists of length 0 or 1, so it should be len(items) <= 1. With >= 1, every non-empty list is returned unsorted, and an empty list would crash at items[0].
Question 2
A for x in items:
B if x < pivot:
C larger.append(x)
D else:
E larger.append(x)
Line C — Items smaller than the pivot belong in the smaller list, so this should be smaller.append(x). Putting them in larger leaves the smaller list empty and the sort is wrong.
Question 3
A def quick_sort(items):
B if len(items) <= 1:
C return items
D pivot = items[len(items)]
E larger = []
Line D — The last valid index is len(items) - 1, so items[len(items)] causes an IndexError. Choose a valid pivot such as items[0].
Question 4
A data = [5, 3, 5, 1, 3]
B result = quick_sort[data]
C print(result)
D # expect [1, 3, 3, 5, 5]
Line B — A function is called with round brackets, not square brackets. It should be result = quick_sort(data).
Question 5
A def quick_sort(items):
B if len(items) <= 1:
C return []
D pivot = items[0]
E smaller = []
F larger = []
Line C — The base case must return the list it was given (items). Returning [] throws away the single item, so values disappear from the sorted result.

Student with a class code? Join your class →