Understand and explain how the merge sort algorithm works.

The idea

Merge sort is a divide-and-conquer algorithm. To sort a list, repeatedly split it into halves until each sublist holds one item; a single item is already sorted. Then merge pairs of sublists back together: compare the front items of the two lists, copy the smaller to the output, and advance that list. Repeat until one list is exhausted, then append the remaining items. Each merge produces a sorted sublist, so the final merge yields the fully sorted list. For example, splitting [5, 2, 9, 1] gives [5, 2] and [9, 1], then [5], [2], [9], [1]; merging [5] with [2] gives [2, 5], merging [9] with [1] gives [1, 9], and merging [2, 5] with [1, 9] gives [1, 2, 5, 9]. The mechanics are the repeated halving and the ordered merging of sorted sublists.

What earns the marks

• Identifies merge sort as a divide-and-conquer algorithm that splits the list into smaller sublists.
• States that splitting continues until each sublist contains a single item, which is already sorted.
• Describes merging two sorted sublists by repeatedly comparing their front items and placing the smaller one next.
• Explains that when one sublist is exhausted, the remaining items of the other are appended.
• Recognises that each merge produces a larger sorted sublist, so the final merge gives the fully sorted list.
• Applies the mechanics to a small example, showing the split stage and the ordered merge stage.

Common mistakes and how to put them right

• Thinking merge sort swaps adjacent items in place like bubble sort.

  Put it right: Merge sort divides the list into halves and merges sorted sublists into a new ordered sequence.

• Believing the list is sorted during the splitting stage.

  Put it right: Splitting only separates items, and ordering happens during the merging stage.

• Merging by simply joining the two sublists end to end.

  Put it right: Items must be compared and placed in ascending order during each merge.

• Stopping the split before single-item sublists.

  Put it right: Halving continues until each sublist has one item, the base case.

Exam tips

• Learn the two stages by name: splitting (divide) and merging (conquer), and be ready to describe each in order.
• Practise tracing a short list such as [5, 2, 9, 1] through every split and merge so you can follow the mechanics accurately.
• When describing a merge, say that the front items of the two sorted sublists are compared and the smaller is copied next.
• Check that your final merged list is in the required order before selecting or writing your answer.