Merge Sort

Merge sort is a divide-and-conquer algorithm. It keeps splitting a list into smaller sub-lists until every sub-list holds just one item. A sub-list with one item is already sorted, so this gives you a set of tiny sorted lists to work with.

Merge sort then merges sorted sub-lists back together in pairs. To merge two sorted lists, compare the next item in each list and write the smaller one to the output list. Move forward in the list that supplied that item, then compare the next pair. Keep going until every item from both lists has been written to the output list. The result is one sorted list.

Those merged lists are paired up again, and the merging continues until a single fully sorted list remains.

Worked example

Start with the scores [7, 2, 9, 4]. Splitting gives [7], [2], [9] and [4].

Merge [7] with [2]: compare 7 and 2, write 2, then write 7, giving [2, 7]. Merge [9] with [4]: compare 9 and 4, write 4, then write 9, giving [4, 9].

Now merge [2, 7] with [4, 9]:

Step	Compare	Write	Output
1	2 and 4	2	`[2]`
2	7 and 4	4	`[2, 4]`
3	7 and 9	7	`[2, 4, 7]`
4	9 is left	9	`[2, 4, 7, 9]`

Merge sort of [7, 2, 9, 4]: the list is split into [7, 2] and [9, 4], then into single items [7], [2], [9], [4]. They are merged in pairs into [2, 7] and [4, 9] (writing the smaller item first), then merged into the final sorted list [2, 4, 7, 9].

The final sorted list is [2, 4, 7, 9].

Worked example

Practise this