Sorting: Bubble and Merge
Why Sorting Matters
Sorting is one of the most studied problems in computer science. A sorted list unlocks binary search, makes data easier to present to users, and is a prerequisite for many other algorithms. Your exam covers two sorting algorithms: bubble sort and merge sort. You need to trace both by hand and compare their efficiency.
Bubble Sort
Bubble sort gets its name because larger values “bubble” towards the end of the list with each pass. In each pass, the algorithm compares pairs of adjacent items and swaps them if they are in the wrong order. After each pass, the largest unsorted item is guaranteed to be in its correct position at the end.
Here is bubble sort in pseudocode:
SET n = LENGTH(list)
FOR pass = 1 TO n - 1
FOR i = 0 TO n - pass - 1
IF list[i] > list[i + 1] THEN
SET temp = list[i]
SET list[i] = list[i + 1]
SET list[i + 1] = temp
END IF
NEXT i
NEXT passNotice the three-variable swap using temp. This is the classic pattern: you cannot swap two values directly without a temporary variable, or one value overwrites the other before it is saved.
List to sort: [5, 3, 8, 1, 4]
Pass 1: Compare pairs left to right.
| Comparison | Swap? | List after |
|---|---|---|
| 5 vs 3 | Yes | [3, 5, 8, 1, 4] |
| 5 vs 8 | No | [3, 5, 8, 1, 4] |
| 8 vs 1 | Yes | [3, 5, 1, 8, 4] |
| 8 vs 4 | Yes | [3, 5, 1, 4, 8] |
After Pass 1: [3, 5, 1, 4, 8] — 8 is now in its final position.
Pass 2: Only compare the first four items.
| Comparison | Swap? | List after |
|---|---|---|
| 3 vs 5 | No | [3, 5, 1, 4, 8] |
| 5 vs 1 | Yes | [3, 1, 5, 4, 8] |
| 5 vs 4 | Yes | [3, 1, 4, 5, 8] |
After Pass 2: [3, 1, 4, 5, 8]. Continue until no swaps occur in a pass.
Bubble sort has a worst-case time complexity of O(n2): for a list of n items, it may need up to approximately n2 comparisons. This makes it slow for large lists. The best case is O(n) when the list is already sorted (one pass with no swaps confirms it is sorted).
Merge Sort
Merge sort is a divide-and-conquer algorithm. It works in two distinct phases: first it splits the list into halves repeatedly until every sub-list has just one item, then it merges the sub-lists back together in sorted order. A single-item list is always sorted by definition, which is why splitting all the way down works.
List: [5, 3, 8, 1]
Split phase:
Stage 1: [5, 3] | [8, 1]
Stage 2: [5] | [3] | [8] | [1]
Merge phase (compare and combine in order):
Merge [5] and [3]: compare 5 and 3 → take 3 first → [3, 5]
Merge [8] and [1]: compare 8 and 1 → take 1 first → [1, 8]
Merge [3, 5] and [1, 8]:
| Left pointer | Right pointer | Smaller taken | Output so far |
|---|---|---|---|
| 3 | 1 | 1 (right) | [1] |
| 3 | 8 | 3 (left) | [1, 3] |
| 5 | 8 | 5 (left) | [1, 3, 5] |
| — | 8 | 8 (right) | [1, 3, 5, 8] |
Result: [1, 3, 5, 8] — fully sorted.
Merge sort has a worst-case time complexity of O(n log n). It splits the list in log n levels and does n comparisons per merge level. This is significantly more efficient than bubble sort’s O(n2) for large datasets, which is why merge sort is used in many real-world applications.
Comparing Bubble Sort and Merge Sort
In exam “compare” questions, do not just describe each algorithm separately — make explicit contrasts using “unlike” or “whereas.”
| Feature | Bubble sort | Merge sort |
|---|---|---|
| Worst-case complexity | O(n2) | O(n log n) |
| Strategy | Repeatedly swap adjacent items | Divide and conquer: split then merge |
| Memory use | In-place (little extra memory) | Needs extra memory for merged sub-lists |
| Ease of implementation | Simple to write and understand | More complex, especially the merge step |
| Performance on small lists | Acceptable | Overhead of splitting may not be worth it |
| Performance on large lists | Very slow | Much faster |