3.1.4 - Merge sort and sort comparisons

Splitting into smaller lists

Merge sort repeatedly splits a list into smaller lists until each contains a single item, then merges those lists back together in order.

Start with [8, 3, 6, 1, 7, 2, 5, 4]. Split it into [8, 3, 6, 1] and [7, 2, 5, 4]. Split each half into two pairs, then split the pairs into single items. Splitting follows positions in the list; it does not move small values to one half and large values to the other.

The split stages preserve the original values and order within each smaller list. The merge stages then produce ordered pairs, ordered four-item lists and finally the complete ordered list.

A single-item list is already sorted because there is no pair of items in the wrong order. These lists provide the starting point for merging. Splitting alone has not sorted the original collection: its single items still appear in the original sequence 8, 3, 6, 1, 7, 2, 5, 4 across the diagram.

Merging 8 with 3 produces [3, 8]; merging 6 with 1 produces [1, 6]. The other pairs become [2, 7] and [4, 5]. Merging the first two ordered pairs gives [1, 3, 6, 8]; merging the other two gives [2, 4, 5, 7]. The final merge produces [1, 2, 3, 4, 5, 6, 7, 8].

If a list has an odd number of items, one split portion can have one more item than the other. The method still works: its merge step can combine ordered lists of different lengths. An empty or single-item list already needs no sorting.

Merging ordered lists

To merge two ordered lists, repeatedly compare their first unconsumed items, take the smaller item and advance only in the list from which it was taken.

For the final merge in the diagram, the left list is [1, 3, 6, 8] and the right list is [2, 4, 5, 7]. Track the next unused position in each list:

The right list is now exhausted. Append the remaining 8 from the left list without another comparison between fronts. The final result is [1, 2, 3, 4, 5, 6, 7, 8], using seven front-item comparisons for this merge.

Taking the smaller front item is justified because each source list is already ordered: no later item in either list can be smaller than its own front item. After taking an item, leave the other list's front where it is. Advancing both positions would skip a value. If the front values are equal, either may be taken next for numerical ascending order, but both copies must eventually appear in the result. This demonstration takes from the left on equality.

The Python Study demonstration performs one merge of two already sorted lists. It demonstrates the operation used at each merge stage; it does not itself perform the preceding splits. .append(...) adds an item to the end of the new result list. The two final loops copy any remaining items after one source list is exhausted.

Choosing a sorting method

Bubble sort and merge sort can both produce the same sorted data, but they create order through different operations and have different practical advantages.

Merge sort's time advantage on large lists comes from combining ordered smaller lists through a limited number of stages. During a merge, each item is taken once into the result, rather than repeatedly swapping it past neighbors. Bubble sort may need many passes, each making numerous comparisons and swaps.

Bubble sort can be easier to implement and can suit a small list; its no-swap optimisation also helps if the data is already sorted. A usual array merge sort needs additional lists during merging, whereas bubble sort can rearrange the existing array with little extra storage. These are qualitative tradeoffs, not a requirement to calculate formal time or space complexity.

For thousands of regularly sorted records, with enough additional storage available, merge sort is usually a suitable choice because time matters and the larger list makes bubble sort's repeated work costly. For a short classroom list, a simple bubble-sort implementation may be quite adequate. State the reason that fits the task; “merge sort is better” alone does not explain a choice.