Sorting Algorithms

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: $O(n^2)$ — all elements in reverse order
• Best case: $O(n^2)$ for the basic version above; $O(n)$ with early termination (see slide 3)
• Space: $O(1)$ — in-place; no extra array needed

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).

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 $O(n)$.

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: ${\log }_{2}7\approx 3$ levels.

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 $n$ takes $O(n)$ comparisons (compare front elements, take the smaller).

Complexity:

• All cases: $O(n\log n)$ — $\log n$ levels of division × $O(n)$ work per level
• Space: $O(n)$ — 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	Merge sort
Time complexity	$O(n^2)$ worst/average	$O(n\log n)$ all cases
Space complexity	$O(1)$ — in-place	$O(n)$ — needs extra array
Stable	Yes	Yes
Simple to implement	Yes	More complex
Best for	Small or nearly sorted datasets	Large 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 $O(n\log n)$ vs $O(n^2)$. For a 1000-element array:

• Bubble sort: up to $10^6$ comparisons
• Merge sort: about $10,000$ comparisons

1. Stopping the bubble sort trace too early

Bubble sort always runs $n-1$ 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 $O(n^2)$; merge sort is $O(n\log n)$. Claiming merge sort is $O(n^2)$ or bubble sort is $O(n\log n)$ 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.