Sorting Algorithms: Bubble Sort and Merge Sort
Why Sort Data?
Sorting data into order is a fundamental computing task. Binary search requires sorted data. Databases display results in a meaningful order. A music app shows albums alphabetically. A leaderboard ranks scores from highest to lowest. The specification requires you to know two sorting algorithms: bubble sort and merge sort. You must understand how each works and be able to compare them.
Bubble Sort
Bubble sort works by repeatedly comparing adjacent pairs of items and swapping them if they are in the wrong order. After the first pass, the largest item has “bubbled” to the last position. After the second pass, the second largest is in place. The algorithm continues until a complete pass produces no swaps — which means the list is sorted.
The mechanics, step by step: Compare items at positions 1 and 2 — swap if needed. Compare positions 2 and 3 — swap if needed. Continue to the end of the list. That completes one pass. Repeat passes until no swaps occur.
Advantages of bubble sort: Simple to understand and implement. Sorts in place (no extra memory needed). Can detect an already-sorted list early (zero swaps on the first pass). Disadvantages: Very slow for large datasets — many passes and many comparisons are needed. Inefficient even in the average case.
Start: [5, 3, 8, 1, 4]
Pass 1:
Compare 5,3 → swap → [3, 5, 8, 1, 4]
Compare 5,8 → no swap → [3, 5, 8, 1, 4]
Compare 8,1 → swap → [3, 5, 1, 8, 4]
Compare 8,4 → swap → [3, 5, 1, 4, 8]
End of pass 1: largest item (8) is now in position 5.
Pass 2:
Compare 3,5 → no swap
Compare 5,1 → swap → [3, 1, 5, 4, 8]
Compare 5,4 → swap → [3, 1, 4, 5, 8]
End of pass 2: [3, 1, 4, 5, 8]
Pass 3:
Compare 3,1 → swap → [1, 3, 4, 5, 8]
Compare 3,4 → no swap
End of pass 3: [1, 3, 4, 5, 8]
Pass 4: No swaps — list is sorted. Algorithm stops. Final list: [1, 3, 4, 5, 8]
Merge Sort
Merge sort uses a divide-and-conquer approach. It repeatedly splits the list in half until each sub-list contains a single item. A list of one item is inherently sorted. It then merges pairs of sub-lists back together, placing items in the correct order during each merge. The merge phase is where the actual sorting happens.
Split phase:
Pass 1: [38, 27, 43, 3] and [9, 82, 10]
Pass 2: [38, 27] | [43, 3] | [9, 82] | [10]
Pass 3: [38] | [27] | [43] | [3] | [9] | [82] | [10]
Merge phase (working back up):
Merge [38] and [27] → [27, 38]
Merge [43] and [3] → [3, 43]
Merge [9] and [82] → [9, 82]
[10] remains [10]
Merge [27, 38] and [3, 43] → [3, 27, 38, 43]
Merge [9, 82] and [10] → [9, 10, 82]
Final merge: [3, 27, 38, 43] and [9, 10, 82] → [3, 9, 10, 27, 38, 43, 82]
The list is now fully sorted. Note how each merge step compares the first elements of the two sub-lists and picks the smaller one.
Advantages of merge sort: Much faster than bubble sort for large datasets. Consistent performance regardless of how the data is initially ordered. Disadvantages: Requires extra memory to store the temporary sub-lists during the merging process. More complex to implement than bubble sort.
Comparing Bubble Sort and Merge Sort
The two algorithms make a direct trade-off between simplicity and speed. Bubble sort is easy to code and uses no extra memory, but it becomes far too slow once the list is large. Merge sort is consistently fast even on very large lists, but it requires extra memory for the sub-lists and is harder to implement correctly.
As with searching algorithms, the right choice depends on the context. For a small list of exam results in a classroom app, bubble sort is perfectly adequate. For sorting millions of customer records in a bank’s database overnight, merge sort (or a similar efficient algorithm) is essential.
Bubble sort:
- Simple to implement
- Sorts in place — no extra memory required
- Can detect already-sorted list early
- Slow for large or randomly ordered data
Merge sort:
- More complex to implement
- Requires extra memory for sub-lists
- Consistent performance regardless of initial order
- Much faster for large datasets