Sorting Algorithms

GCSE Computer Science · Algorithms

Sorting Algorithms

Sorting algorithms arrange data into a specific order (usually ascending). You must know bubble sort, merge sort, and insertion sort for the AQA exam.

---

Bubble Sort

Bubble sort repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. Each pass "bubbles" the largest unsorted value to its correct position.

Pseudocode

FUNCTION bubbleSort(list)
    n = LEN(list)
    FOR i = 0 TO n - 2
        swapped = FALSE
        FOR j = 0 TO n - 2 - i
            IF list[j] > list[j + 1] THEN
                SWAP list[j] AND list[j + 1]
                swapped = TRUE
            END IF
        END FOR
        IF swapped == FALSE THEN
            BREAK
        END IF
    END FOR
    RETURN list
END FUNCTION

Walkthrough

Sorting [5, 3, 8, 1]:

Pass	Comparisons	Result
1	5>3 swap, 5<8 no, 8>1 swap	[3, 5, 1, 8]
2	3<5 no, 5>1 swap	[3, 1, 5, 8]
3	3>1 swap	[1, 3, 5, 8]

Properties

Time complexity: Best O(n), Average O(n²), Worst O(n²)
Space complexity: O(1) — sorts in place
Stable: Yes (equal elements keep their original order)

---

Merge Sort

Merge sort uses a divide and conquer strategy. It splits the list into halves recursively until each sub-list has one element, then merges them back in order.

Pseudocode

FUNCTION mergeSort(list)
    IF LEN(list) <= 1 THEN
        RETURN list
    END IF
    mid = LEN(list) DIV 2
    left = mergeSort(list[0:mid])
    right = mergeSort(list[mid:end])
    RETURN merge(left, right)
END FUNCTION

FUNCTION merge(left, right)
    result = []
    WHILE left NOT EMPTY AND right NOT EMPTY
        IF left[0] <= right[0] THEN
            APPEND left[0] TO result
            REMOVE left[0]
        ELSE
            APPEND right[0] TO result
            REMOVE right[0]
        END IF
    END WHILE
    APPEND remaining left TO result
    APPEND remaining right TO result
    RETURN result
END FUNCTION

Walkthrough

Sorting [5, 3, 8, 1]:

1. Split: [5, 3, 8, 1] → [5, 3] and [8, 1]

2. Split again: [5] [3] and [8] [1]

3. Merge: [3, 5] and [1, 8]

4. Merge: [1, 3, 5, 8]

Properties

Time complexity: Best O(n log n), Average O(n log n), Worst O(n log n)
Space complexity: O(n) — needs extra memory for sub-lists
Stable: Yes

---

Insertion Sort

Insertion sort builds the sorted list one item at a time. It takes each element and inserts it into the correct position among the already-sorted elements.

Pseudocode

FUNCTION insertionSort(list)
    FOR i = 1 TO LEN(list) - 1
        key = list[i]
        j = i - 1
        WHILE j >= 0 AND list[j] > key
            list[j + 1] = list[j]
            j = j - 1
        END WHILE
        list[j + 1] = key
    END FOR
    RETURN list
END FUNCTION

Walkthrough

Sorting [5, 3, 8, 1]:

Step	Key	Action	Result
1	3	Insert before 5	[3, 5, 8, 1]
2	8	Already in place	[3, 5, 8, 1]
3	1	Insert before 3	[1, 3, 5, 8]

Properties

Time complexity: Best O(n), Average O(n²), Worst O(n²)
Space complexity: O(1) — sorts in place
Stable: Yes

---

Comparison Table

Feature	Bubble Sort	Merge Sort	Insertion Sort
Best case	O(n)	O(n log n)	O(n)
Worst case	O(n²)	O(n log n)	O(n²)
Space	O(1)	O(n)	O(1)
In-place?	Yes	No	Yes
Stable?	Yes	Yes	Yes
Best for	Nearly sorted, small lists	Large datasets	Small or nearly sorted lists

---

Exam Tips

Merge sort is the most efficient for large datasets but uses more memory
Bubble sort and insertion sort are efficient on nearly sorted data (best case O(n))
When asked to trace a sort, show the state of the list after each pass or step
A common 6-mark question asks you to compare two sorting algorithms — always discuss time complexity, space complexity, and suitability for the scenario

Sorting Algorithms