Merge Sort

Merge sort is a sorting algorithm that uses a divide-and-conquer strategy: it splits a list into smaller pieces, and then merges those pieces back together in sorted order.

Unlike bubble sort — which repeatedly compares adjacent elements across the whole list — merge sort never compares elements from the full unsorted list directly. Every merge step takes two already-sorted sub-lists and combines them into one sorted output.

Merge sort runs in two distinct phases:

1. Split — divide the list in half repeatedly until every sub-list contains exactly one element
2. Merge — combine pairs of sorted sub-lists into progressively larger sorted lists, until the full list is reassembled

A list of one element is sorted by definition — this is the base case that terminates the splitting.

Starting with the full list, merge sort divides it in half at each level until every sub-list contains a single element.

Example — split [38, 12, 45, 9, 22, 7]:

After splitting: [38] [12] [45] [9] [22] [7]

Each sub-list has one element and is trivially sorted. The split phase produces $\lceil {\log }_{2}n\rceil$ levels of division. For 6 elements: $\lceil {\log }_{2}6\rceil =3$ levels.

The split phase does no comparisons — it only divides the list. All the comparison work happens during the merge phase.

Merging takes two sorted sub-lists and produces one sorted output by repeatedly selecting the smaller of the two front elements.

Merging [12] and [45]:

Left remaining	Right remaining	Action	Output so far
12	45	Take 12 (smaller)	[12]
—	45	Left exhausted — take all of right	[12, 45]

Result: [12, 45] ✓

Merging [22] and [7]:

Left remaining	Right remaining	Action	Output so far
22	7	Take 7 (smaller)	[7]
22	—	Right exhausted — take all of left	[7, 22]

Result: [7, 22] ✓

When one sub-list is exhausted, all remaining elements of the other sub-list are appended in order — no further comparisons are needed because that sub-list is already sorted.

Single-element merges are straightforward. Merging two multi-element sorted sub-lists follows the same rule — always take the smaller front element — but requires more steps.

Merging [9] and [7, 22]:

Left remaining	Right remaining	Action	Output so far
9	7, 22	Take 7 (smaller)	[7]
9	22	Take 9 (smaller)	[7, 9]
—	22	Left exhausted — take all of right	[7, 9, 22]

Result: [7, 9, 22] ✓

Merging [38] and [12, 45]:

Left remaining	Right remaining	Action	Output so far
38	12, 45	Take 12 (smaller)	[12]
38	45	Take 38 (smaller)	[12, 38]
—	45	Left exhausted — take all of right	[12, 38, 45]

Result: [12, 38, 45] ✓

The key point: once one sub-list is exhausted, the remaining elements of the other sub-list are appended without further comparisons, because they are already in order.

Sort [38, 12, 45, 9, 22, 7] using merge sort.

Split phase (top-down) produces six single-element sub-lists: [38] [12] [45] [9] [22] [7]

Merge phase (bottom-up, following the split tree):

Step	Sub-lists being merged	Result
1	[12] + [45]	[12, 45]
2	[38] + [12, 45]	[12, 38, 45]
3	[22] + [7]	[7, 22]
4	[9] + [7, 22]	[7, 9, 22]
5	[12, 38, 45] + [7, 9, 22]	[7, 9, 12, 22, 38, 45]

Step 5 in detail — merging [12, 38, 45] and [7, 9, 22]:

Left remaining	Right remaining	Action	Output so far
12, 38, 45	7, 9, 22	Take 7	[7]
12, 38, 45	9, 22	Take 9	[7, 9]
12, 38, 45	22	Take 12	[7, 9, 12]
38, 45	22	Take 22	[7, 9, 12, 22]
38, 45	—	Right exhausted — append left	[7, 9, 12, 22, 38, 45]

Final sorted list: [7, 9, 12, 22, 38, 45] ✓

Both algorithms sort a list, but their performance on large datasets differs enormously.

Property	Merge sort	Bubble sort
Worst-case comparisons	$O(n\log n)$	$O(n^2)$
Best-case comparisons	$O(n\log n)$	$O(n)$ (optimised, already sorted)
For $n=100$	~700	~10,000
For $n=10,000$	~130,000	~100,000,000
Extra memory needed	Yes — sub-lists during merge	No — sorts in place

$O(n\log n)$ means the number of comparisons grows proportionally to $n$ multiplied by ${\log }_2(n)$. $O(n^2)$ means it grows with the square of $n$ — far faster.

An optimised bubble sort implementation includes an early-exit flag that detects when no swaps occurred in a pass, allowing it to terminate in a single pass on an already-sorted list ($O(n)$ best case). Without this optimisation, bubble sort always runs $O(n^2)$ passes. Merge sort always performs the full split-and-merge regardless of initial order.

For large datasets, merge sort is consistently faster than bubble sort. The trade-off is memory: merge sort needs additional space proportional to n for the sub-lists during merging, while bubble sort sorts in place.

1. Describing the merge before the split

The split always comes first. The entire point of splitting is to produce single-element lists that are trivially sorted — without the split, there are no sorted sub-lists to merge.

2. Confusing the merge step with a re-sort

Merging works correctly because both input sub-lists are already sorted. The algorithm takes the smaller front element from either list — it does not sort either sub-list during the merge. Answers that say "arrange the elements in order" miss this mechanism.

3. Getting the number of split levels wrong

For $n$ elements the number of split levels is $\lceil {\log }_{2}n\rceil$. For 8 elements: ${\log }_{2}8=3$ levels exactly. For 6 elements: ${\log }_{2}6\approx 2.58$, so $\lceil 2.58\rceil =3$ levels.

4. Stating merge sort uses less memory than bubble sort

The opposite is true. Merge sort requires additional memory proportional to n for the sub-lists created during merging. Bubble sort is in-place — it uses only the original list with no extra allocations.

5. Claiming bubble sort is always slower

An optimised bubble sort with an early-exit flag runs in $O(n)$ on an already-sorted list; merge sort always runs $O(n\log n)$. On small or nearly-sorted datasets, an optimised bubble sort can outperform merge sort. The comparison depends on the data and whether the early-exit optimisation is implemented.