Sorting Algorithms in Python: Bubble, Merge, Quick

Why Sorting Appears in HKDSE

HKDSE ICT tests sorting algorithms to assess algorithmic thinking. You should be able to implement at least bubble sort and explain merge and quick sort.

1. Bubble Sort

Repeatedly swap adjacent elements if they're in wrong order. Simple but slow.

def bubble_sort(lst):
    n = len(lst)
    for i in range(n):
        for j in range(n - 1 - i):
            if lst[j] > lst[j + 1]:
                lst[j], lst[j + 1] = lst[j + 1], lst[j]
    return lst

print(bubble_sort([5, 2, 8, 1, 9, 3]))
# [1, 2, 3, 5, 8, 9]

Complexity

• Time: O(n²)
• Space: O(1)

Optimisation: Early Exit

def bubble_sort(lst):
    n = len(lst)
    for i in range(n):
        swapped = False
        for j in range(n - 1 - i):
            if lst[j] > lst[j + 1]:
                lst[j], lst[j + 1] = lst[j + 1], lst[j]
                swapped = True
        if not swapped:
            break   # already sorted
    return lst

2. Selection Sort

Find minimum, put it at front, repeat.

def selection_sort(lst):
    n = len(lst)
    for i in range(n):
        min_idx = i
        for j in range(i + 1, n):
            if lst[j] < lst[min_idx]:
                min_idx = j
        lst[i], lst[min_idx] = lst[min_idx], lst[i]
    return lst

3. Insertion Sort

Build sorted portion by inserting each element in correct position.

def insertion_sort(lst):
    for i in range(1, len(lst)):
        key = lst[i]
        j = i - 1
        while j >= 0 and lst[j] > key:
            lst[j + 1] = lst[j]
            j -= 1
        lst[j + 1] = key
    return lst

4. Merge Sort

Divide list in half, sort each half, merge them. Much faster — O(n log n).

def merge_sort(lst):
    if len(lst) <= 1:
        return lst
    mid = len(lst) // 2
    left = merge_sort(lst[:mid])
    right = merge_sort(lst[mid:])
    return merge(left, right)

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

5. Quick Sort

Pick a pivot, partition list around it, recursively sort partitions. Fast average O(n log n).

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

Python's Built-In Sort

In real code, use sorted() or .sort(). Python uses Timsort internally — highly optimised.

lst = [5, 2, 8, 1]
sorted(lst)          # returns new sorted list
lst.sort()           # sorts in place

# Descending
sorted(lst, reverse=True)

# Custom key
students = [("Chan", 85), ("Lee", 72)]
sorted(students, key=lambda x: x[1])   # sort by score

HKDSE Focus

For HKDSE, bubble sort is the most commonly tested. You must be able to:

• Implement bubble sort from scratch
• Trace through its execution
• Explain why it's O(n²)
• Use Python's built-in sort for non-algorithm questions