Insertion, merge and quick sort: trace the method

Insertion sort: keep the prefix sorted

Treat the first item as a sorted prefix. Each pass inserts one new item into that prefix, leaving the unprocessed suffix for later passes.

Merge sort: split, sort, merge

A zero- or one-item list is already sorted. Otherwise split by position at len(values) // 2, sort the smaller lists and combine their results. Repeating the same task on smaller inputs is divide and conquer.

Quick sort: define the pivot and partition

This in-place version uses a Lomuto-style partition with inclusive low and high bounds. The last item is the pivot. A question's supplied convention takes precedence.

After placing pivot index 2, recurse on 0..1 and 3..5. Empty and one-item ranges do nothing because low < high is false.

Continue the specified recursive ranges even if the list looks sorted. A self-swap also leaves the displayed list unchanged, while still being an executed step.

Compare the versions shown on this page

*Average cases here assume random permutations of distinct input items. They are not guarantees for arbitrary incoming data. Auxiliary space excludes the supplied input but includes temporary lists, returned storage and recursive call frames.

Insertion: count the shifts

• Sorted input: one failed ordering check per insertion, no shifts, giving O(n).
• Reverse order: 1 + 2 + … + (n − 1) shifts, giving O(n²). Nearly sorted input often needs few shifts.
• Memory: a saved key and a fixed number of indexes, giving O(1) auxiliary space.

Merge: work at every split level

O(log n) levels each do O(n) total merging work. This version still splits and merges sorted input. Peak temporary lists take O(n) space; O(log n) call frames do not change that overall space class.

Quick: balance determines depth

Equal values also cause poor partitions under this <= rule. Other pivots or three-way partitioning change that behaviour. Versions allocating separate smaller/larger lists have extra storage costs; answer memory questions using the supplied implementation.

What else matters when choosing a sort?

A stable sort preserves the relative order of equal-key records. Equal scores might therefore retain an earlier name order.

• Insertion shifts only strictly greater items, preserving ties.
• Merge takes the left item on equality, preserving ties when the rule is applied consistently to records and their keys.
• This quick sort is generally unstable: swaps can move equal-key records past each other.

Original A-Level practice

These four original questions total 19 marks. Use the algorithms and conventions on this page. The marking guidance is indicative and independently written.

Optional Python implementations

Use these after learning the rules and tracing the examples. Insertion and quick sort change the supplied list; merge sort returns a new list. Each uses the exact conventions shown above.

def insertion_sort(values):
    # Sort the supplied list in place.
    for index in range(1, len(values)):
        key = values[index]
        position = index - 1
        while position >= 0 and values[position] > key:
            values[position + 1] = values[position]
            position = position - 1
        values[position + 1] = key


numbers = [5, 2, 8, 1, 6, 3]
insertion_sort(numbers)
print(numbers)  # [1, 2, 3, 5, 6, 8]

def merge(left, right):
    result = []
    left_index = 0
    right_index = 0
    while left_index < len(left) and right_index < len(right):
        if left[left_index] <= right[right_index]:
            result.append(left[left_index])
            left_index = left_index + 1
        else:
            result.append(right[right_index])
            right_index = right_index + 1
    result.extend(left[left_index:])
    result.extend(right[right_index:])
    return result


def merge_sort(values):
    # Return a new sorted list; leave the supplied list unchanged.
    if len(values) <= 1:
        return values[:]
    middle = len(values) // 2
    left = merge_sort(values[:middle])
    right = merge_sort(values[middle:])
    return merge(left, right)


numbers = [5, 2, 8, 1, 6, 3]
print(merge_sort(numbers))  # [1, 2, 3, 5, 6, 8]
print(numbers)             # [5, 2, 8, 1, 6, 3]

def partition(values, low, high):
    # Last item is the pivot; low and high are inclusive.
    pivot = values[high]
    boundary = low
    for scan in range(low, high):
        if values[scan] <= pivot:
            values[boundary], values[scan] = (
                values[scan], values[boundary]
            )
            boundary = boundary + 1
    values[boundary], values[high] = (
        values[high], values[boundary]
    )
    return boundary


def quick_sort(values, low, high):
    # Sort the inclusive range in place, left subrange first.
    if low < high:
        pivot_index = partition(values, low, high)
        quick_sort(values, low, pivot_index - 1)
        quick_sort(values, pivot_index + 1, high)


numbers = [5, 2, 8, 1, 6, 3]
quick_sort(numbers, 0, len(numbers) - 1)
print(numbers)  # [1, 2, 3, 5, 6, 8]