Intermediate

Sorting Algorithms

AicademyAicademy
·A-Level Computer Science·AQA 7517·5 min
4.3.5 Sorting algorithms

Bubble Sort

Bubble sort repeatedly compares adjacent elements and swaps them if they are in the wrong order. After each complete pass, the largest unsorted element "bubbles" to its correct position at the end.

PROCEDURE bubbleSort(arr)
    n ← LEN(arr)
    FOR i ← 1 TO n - 1
        FOR j ← 1 TO n - i
            IF arr[j] > arr[j + 1] THEN
                temp      ← arr[j]
                arr[j]    ← arr[j + 1]
                arr[j + 1] ← temp
            ENDIF
        NEXT j
    NEXT i
ENDPROCEDURE

The inner loop runs one fewer iteration per outer pass because the last i elements are already sorted.

Complexity:

  • Worst case: — all elements in reverse order
  • Best case: for the basic version above; with early termination (see slide 3)
  • Space: — in-place; no extra array needed

Bubble Sort Trace

Sort [64, 25, 12, 22, 11]:

Pass 1 (bubble largest to end):

  • 64 > 25 → swap: [25, 64, 12, 22, 11]
  • 64 > 12 → swap: [25, 12, 64, 22, 11]
  • 64 > 22 → swap: [25, 12, 22, 64, 11]
  • 64 > 11 → swap: [25, 12, 22, 11, 64]

Pass 2:

  • 25 > 12 → swap: [12, 25, 22, 11, 64]
  • 25 > 22 → swap: [12, 22, 25, 11, 64]
  • 25 > 11 → swap: [12, 22, 11, 25, 64]

Pass 3:

  • 12 < 22 → no swap: [12, 22, 11, 25, 64]
  • 22 > 11 → swap: [12, 11, 22, 25, 64]

Pass 4:

  • 12 > 11 → swap: [11, 12, 22, 25, 64]

Sorted: [11, 12, 22, 25, 64] after 4 passes (n − 1 passes for n = 5).

Optimised Bubble Sort

A simple optimisation adds a swapped flag: if a complete pass makes no swaps, the array is already sorted and the algorithm can terminate early.

PROCEDURE bubbleSortOptimised(arr)
    n ← LEN(arr)
    FOR i ← 1 TO n - 1
        swapped ← False
        FOR j ← 1 TO n - i
            IF arr[j] > arr[j + 1] THEN
                temp       ← arr[j]
                arr[j]     ← arr[j + 1]
                arr[j + 1] ← temp
                swapped    ← True
            ENDIF
        NEXT j
        IF NOT swapped THEN
            RETURN    // Array is sorted; no need to continue
        ENDIF
    NEXT i
ENDPROCEDURE

With this optimisation, sorting an already-sorted array takes only one pass: best case .

Merge Sort

Merge sort is a divide-and-conquer algorithm:

  1. Divide: split the array in half recursively until every sub-array has one element (a single element is trivially sorted)
  2. Conquer: merge adjacent sorted sub-arrays into one sorted array

A single element is trivially sorted.

Divide phase[38, 27, 43, 3, 9, 82, 10]:

[38, 27, 43, 3, 9, 82, 10]
[38, 27, 43, 3]    [9, 82, 10]
[38, 27]  [43, 3]  [9, 82]  [10]
[38] [27] [43] [3] [9] [82] [10]

Each level halves the sub-arrays: levels.

Something not quite clicking?

Ask Aica to explain any part of this differently. Free, takes 30 seconds.

Ask Aica

Merge Sort — Merge Phase and Complexity

Merge phase — merge sorted sub-arrays back up:

[38] [27] → [27, 38]     [43] [3] → [3, 43]     [9] [82] → [9, 82]     [10]
[27, 38] + [3, 43] → [3, 27, 38, 43]             [9, 82] + [10] → [9, 10, 82]
[3, 27, 38, 43] + [9, 10, 82] → [3, 9, 10, 27, 38, 43, 82]

The merge step — merging two sorted halves of combined length takes comparisons (compare front elements, take the smaller).

Complexity:

  • All cases: levels of division × work per level
  • Space: — requires an auxiliary array for merging
FUNCTION mergeSort(arr)
    IF LEN(arr) <= 1 THEN
        RETURN arr
    ENDIF
    mid    ← LEN(arr) DIV 2
    left   ← mergeSort(arr[1..mid])
    right  ← mergeSort(arr[mid+1..LEN(arr)])
    RETURN merge(left, right)
ENDFUNCTION

FUNCTION merge(left, right)
    result ← []
    WHILE LEN(left) > 0 AND LEN(right) > 0 DO
        IF left[1] <= right[1] THEN
            result.append(left[1])
            left ← left[2..LEN(left)]
        ELSE
            result.append(right[1])
            right ← right[2..LEN(right)]
        ENDIF
    ENDWHILE
    RETURN result + left + right
ENDFUNCTION

Bubble Sort vs Merge Sort

Bubble sortMerge sort
Time complexity worst/average all cases
Space complexity — in-place — needs extra array
StableYesYes
Simple to implementYesMore complex
Best forSmall or nearly sorted datasetsLarge datasets

Stable sort: a sorting algorithm is stable if elements with equal keys retain their original relative order after sorting. Both bubble sort and merge sort are stable.

Practical rule: for exam questions about large datasets, merge sort is the correct choice due to vs . For a 1000-element array:

  • Bubble sort: up to comparisons
  • Merge sort: about comparisons

Common Exam Mistakes

1. Stopping the bubble sort trace too early

Bubble sort always runs passes in the basic version (or until no swap occurs in the optimised version). Stopping after the array "looks sorted" mid-trace loses marks — you must complete the required number of passes.

2. Confusing O(n²) and O(n log n) for the wrong algorithm

Bubble sort is ; merge sort is . Claiming merge sort is or bubble sort is is a basic factual error.

3. Claiming bubble sort needs extra memory

Bubble sort is in-place — it rearranges the original array using only a single temp variable. Merge sort requires an extra array for merging.

4. Forgetting the base case in merge sort

Merge sort is recursive. Without the base case IF LEN(arr) <= 1 THEN RETURN arr, it recurses indefinitely. The base case is what makes the recursion terminate.

5. Not stating the stability of a sort when asked

Both bubble sort and merge sort are stable. If a question asks about stability, explicitly state this and explain what stability means — elements with equal keys keep their original order.

Generate revision on any topic you study

Type any topic you're studying and Aicademy generates a complete lesson, quiz, and flashcard set — personalised to your level.

Lessons on anything

Structured, level-matched lessons on any topic you study

Practice quizzes

Find out what you actually know before the exam does

Flashcard sets

Lock in key concepts with instant revision cards

Ask Aica

Stuck on something? Get a clear explanation, any time

Prev

Searching Algorithms

Next

Dijkstra's Shortest Path Algorithm

Related lessons

6 Slides

Lesson

Searching Algorithms

A-Level Computer Science · AQA 7517

10 hours ago

7 Slides

Lesson

Complexity and Big-O Notation

A-Level Computer Science · AQA 7517

10 hours ago