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]:

[38, 12, 45, 9, 22, 7]
         ↙           ↘
  [38, 12, 45]     [9, 22, 7]
     ↙     ↘          ↙     ↘
  [38]  [12, 45]   [9]   [22, 7]
           ↙  ↘             ↙  ↘
         [12] [45]        [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.