Sorting Algorithms

AQA 7517 requires knowledge of bubble sort, insertion sort, merge sort, and quicksort. You must be able to trace and analyse each.

Bubble Sort

Repeatedly steps through the list, comparing adjacent elements and swapping if they are in the wrong order. After each pass, the largest unsorted element "bubbles" to its correct position.

// Bubble sort — O(n²)
PROCEDURE bubbleSort(arr)
  n ← len(arr)
  FOR i ← 0 TO n-2
    FOR j ← 0 TO n-2-i
      IF arr[j] > arr[j+1] THEN
        SWAP arr[j], arr[j+1]
      END IF
    END FOR
  END FOR
END PROCEDURE

// Trace: [5, 3, 8, 1]
// Pass 1: 3,5,8,1 → 3,5,1,8  (8 placed)
// Pass 2: 3,1,5,8             (5 placed)
// Pass 3: 1,3,5,8             (sorted)

Insertion Sort

Builds a sorted sublist one element at a time by taking each element and inserting it into its correct position among the already-sorted elements.

// Insertion sort — O(n²) worst, O(n) best (already sorted)
PROCEDURE insertionSort(arr)
  FOR i ← 1 TO len(arr)-1
    key ← arr[i]
    j ← i - 1
    WHILE j >= 0 AND arr[j] > key
      arr[j+1] ← arr[j]   // Shift right
      j ← j - 1
    END WHILE
    arr[j+1] ← key         // Insert
  END FOR
END PROCEDURE

// Trace: [5, 3, 8, 1]
// i=1: key=3, shift 5 right → [3,5,8,1]
// i=2: key=8, no shift → [3,5,8,1]
// i=3: key=1, shift 8,5,3 → [1,3,5,8]

Merge Sort

Divide and conquer — recursively split the array in half until single elements, then merge sorted halves back together.

// Merge sort — O(n log n) always
PROCEDURE mergeSort(arr)
  IF len(arr) <= 1 THEN RETURN arr
  mid ← len(arr) DIV 2
  left ← mergeSort(arr[0..mid-1])
  right ← mergeSort(arr[mid..])
  RETURN merge(left, right)
END PROCEDURE

// merge: compare fronts, take smaller, repeat
// Trace: [5,3,8,1]
// Split: [5,3] and [8,1]
// Split: [5],[3] and [8],[1]
// Merge: [3,5] and [1,8]
// Merge: [1,3,5,8] ✓

Quicksort

Divide and conquer — choose a pivot, partition into elements less than and greater than pivot, recursively sort each partition.

// Quicksort — O(n log n) avg, O(n²) worst (bad pivot)
PROCEDURE quicksort(arr, low, high)
  IF low < high THEN
    p ← partition(arr, low, high)
    quicksort(arr, low, p-1)
    quicksort(arr, p+1, high)
  END IF
END PROCEDURE

// Trace: [5,3,8,1,4] pivot=5 (first element)
// Partition: [3,1,4] | 5 | [8]
// Recurse left: [3,1,4] pivot=3 → [1] | 3 | [4]
// Result: [1,3,4,5,8] ✓

Comparison Table