Quicksort

The Big Idea

Quicksort is a divide-and-conquer algorithm. Instead of sorting a list all at once, it:

1. Partitions the list into two halves (values smaller than a chosen pivot, and values larger than it).
2. Recursively sorts each half.
3. Combines the results to form a fully sorted list.

The power of Quicksort comes from recursion: each time it creates smaller versions of the same problem until the problem is trivial (a list of length 0 or 1 is already sorted).

Why Recursion Matters

• Decomposition: A large list is reduced to smaller sublists.
• Self-similarity: Each recursive call applies the same logic (partition, then sort) on a smaller scale.
• Base case: When the list is so small that it doesn’t need sorting, the recursion stops.

Without recursion, the algorithm would be very complex to write. With recursion, Quicksort is elegant and mirrors its own definition.

Step-by-Step Example

Suppose we want to sort [8, 3, 7, 4, 9, 2].

1. Pick a pivot (say, 7).
2. Partition into:
   • Left: [3, 4, 2] (smaller than 7)
   • Right: [8, 9] (greater than 7)
3. Recursively sort [3, 4, 2] and [8, 9].
   • Sorting [3, 4, 2] again chooses a pivot, splits, and recurses…
   • Sorting [8, 9] stops quickly because it’s already small.
4. Combine: [2, 3, 4] + [7] + [8, 9].

Python Implementation

Here’s a clean recursive implementation of Quicksort:

def quicksort(lst):
    # Base case: lists of length 0 or 1 are already sorted
    if len(lst) <= 1:
        return lst

    # Choose a pivot (here we take the first element)
    pivot = lst[0]

    # Partition step
    left = [x for x in lst[1:] if x <= pivot]
    right = [x for x in lst[1:] if x > pivot]

    # Recursive step: sort left and right, then combine
    return quicksort(left) + [pivot] + quicksort(right)


# Example use
numbers = [8, 3, 7, 4, 9, 2]
print(quicksort(numbers))  # Output: [2, 3, 4, 7, 8, 9]

Key Points to Remember

• Partition → Break into smaller problems.
• Recursion → Solve the smaller problems in the same way.
• Base case → Stop when the list is too small to sort.

IB Command Term Focus

A common exam command term here is “Explain”:

• A weak answer: “Quicksort uses recursion to sort lists.” (too vague).
• A good answer: “Quicksort recursively partitions a list into two smaller sublists around a pivot, then sorts each sublist using the same recursive strategy until the base case (lists of size 0 or 1) is reached.”