Merge Sort

Merge sort is an efficient, general-purpose sorting algorithm that uses a divide and conquer strategy. It works by repeatedly splitting a list in half until each sub-list contains a single element, and then merging those sub-lists back together in the correct order.

---

The Divide and Conquer Approach

Merge sort follows three key steps:

1. Divide — Split the list into two halves.
2. Conquer — Recursively sort each half (keep splitting until each sub-list has one element).
3. Combine — Merge the sorted halves back together to produce the final sorted list.

A list of one element is considered already sorted (this is the base case for the recursion).

The recursion tree for sorting [6, 3, 8, 1] looks like:

graph TD
    A["[6, 3, 8, 1]"] --> B["[6, 3]"]
    A --> C["[8, 1]"]
    B --> D["[6]"]
    B --> E["[3]"]
    C --> F["[8]"]
    C --> G["[1]"]
    D --> H["[3, 6]"]
    E --> H
    F --> I["[1, 8]"]
    G --> I
    H --> J["[1, 3, 6, 8]"]
    I --> J

---

Pseudocode for Merge Sort

FUNCTION mergeSort(list)
    IF LENGTH(list) <= 1 THEN
        RETURN list
    ENDIF
    mid = LENGTH(list) DIV 2
    left = mergeSort(list[0 TO mid - 1])
    right = mergeSort(list[mid TO end])
    RETURN merge(left, right)
ENDFUNCTION

FUNCTION merge(left, right)
    result = []
    WHILE left is not empty AND right is not empty
        IF left[0] <= right[0] THEN
            APPEND left[0] to result
            REMOVE first element from left
        ELSE
            APPEND right[0] to result
            REMOVE first element from right
        ENDIF
    ENDWHILE
    APPEND remaining elements of left to result
    APPEND remaining elements of right to result
    RETURN result
ENDFUNCTION

---

Worked Example

Sort the list: [6, 3, 8, 1, 5, 2, 7, 4]

Step 1: Divide

[6, 3, 8, 1, 5, 2, 7, 4]
        /             \
  [6, 3, 8, 1]    [5, 2, 7, 4]
    /      \        /      \
 [6, 3]  [8, 1]  [5, 2]  [7, 4]
  / \     / \     / \     / \
[6] [3] [8] [1] [5] [2] [7] [4]

Each sub-list now contains a single element and is therefore sorted.

Step 2: Merge

Now merge the sub-lists back together in order:

[6] [3] → [3, 6]     [8] [1] → [1, 8]     [5] [2] → [2, 5]     [7] [4] → [4, 7]

[3, 6] [1, 8] → [1, 3, 6, 8]         [2, 5] [4, 7] → [2, 4, 5, 7]

[1, 3, 6, 8] [2, 4, 5, 7] → [1, 2, 3, 4, 5, 6, 7, 8]

Final result: [1, 2, 3, 4, 5, 6, 7, 8]

Detailed Merge: [1, 3, 6, 8] and [2, 4, 5, 7]

Left	Right	Compare	Append	Result so far
1, 3, 6, 8	2, 4, 5, 7	1 < 2	1	[1]
3, 6, 8	2, 4, 5, 7	3 > 2	2	[1, 2]
3, 6, 8	4, 5, 7	3 < 4	3	[1, 2, 3]
6, 8	4, 5, 7	6 > 4	4	[1, 2, 3, 4]
6, 8	5, 7	6 > 5	5	[1, 2, 3, 4, 5]
6, 8	7	6 < 7	6	[1, 2, 3, 4, 5, 6]
8	7	8 > 7	7	[1, 2, 3, 4, 5, 6, 7]
8	(empty)	—	8	[1, 2, 3, 4, 5, 6, 7, 8]

---

Efficiency of Merge Sort

Case	Time Complexity	Explanation
Best case	O(n log n)	Always divides and merges
Worst case	O(n log n)	Same — performance is consistent
Average case	O(n log n)	Always the same

Merge sort is much faster than bubble sort (O(n²)) for large datasets. The trade-off is that it uses additional memory for the temporary sub-lists during merging (space complexity O(n)).

---

Advantages of Merge Sort

• Consistent performance — O(n log n) in all cases
• Very efficient for large datasets
• Stable sort — equal elements maintain their relative order
• Predictable — performance does not depend on the initial order of the data

Disadvantages of Merge Sort

• Uses extra memory — temporary arrays are needed for merging (space complexity O(n))
• More complex to implement than bubble sort or insertion sort
• Slower than bubble sort for very small or nearly sorted datasets due to overhead

Exam Tip: If asked to compare merge sort with bubble sort, mention that merge sort is O(n log n) vs O(n²) for bubble sort, but merge sort requires additional memory. Always show the splitting and merging stages clearly in a trace.

---

Key Points

• Merge sort uses a divide and conquer approach: split, sort recursively, merge.
• Time complexity: O(n log n) in all cases — best, worst, and average.
• Space complexity: O(n) — requires extra memory for merging.
• Much more efficient than bubble sort for large datasets.
• A stable sorting algorithm.

---

Extended Worked Examples

Worked Example A: Detailed Split Tree for [38, 27, 43, 3, 9, 82, 10]

Level 0:              [38, 27, 43, 3, 9, 82, 10]
                        /                \
Level 1:        [38, 27, 43, 3]      [9, 82, 10]
                   /      \             /     \
Level 2:      [38, 27]   [43, 3]    [9, 82]   [10]
                / \      /   \      /   \
Level 3:     [38][27] [43] [3]  [9] [82]

The split tree has log₂(n) levels (here ⌈log₂ 7⌉ = 3). At every level the combined size across all sub-lists is n (= 7), so each merging level performs n comparisons. Total comparisons are therefore n × log₂(n) — this is the source of O(n log n) complexity.

Worked Example B: Full Merge Walk-through

Starting from the singletons, re-merge upwards:

Level 3 → Level 2:

• [38] + [27] → compare 38 vs 27 → take 27, then 38 → [27, 38]
• [43] + [3] → [3, 43]
• [9] + [82] → [9, 82]
• [10] stays alone

Level 2 → Level 1:

Merge [27, 38] and [3, 43]: