Students should know the advantages and disadvantages of both algorithms.

The idea

In section 3.1.4 you study two sorting algorithms, and you must be able to state the advantages and disadvantages of each. Learn what each algorithm does step by step, then attach strengths and weaknesses to that behaviour. A bubble sort repeatedly compares adjacent items and swaps them, so it is simple to write and trace but slow on large lists because it makes many comparisons. A merge sort repeatedly splits a list into halves, sorts the parts and merges them, so it is much faster on large data but needs extra memory for the sub-lists and is harder to code. Practise by sorting a short list such as 5, 2, 9, 1 with each method and counting comparisons and passes, then match each observation to an advantage or disadvantage.

What earns the marks

• Bubble sort compares adjacent pairs and swaps them when out of order, repeating passes until no swaps occur.
• Bubble sort advantage: straightforward to understand, write and trace, and needs little extra memory.
• Bubble sort disadvantage: inefficient on large lists because it performs many comparisons and passes.
• Merge sort splits the list into halves, sorts each half and merges them back together.
• Merge sort advantage: generally faster and more efficient than bubble sort on large data sets.
• Merge sort disadvantage: requires additional memory for the divided sub-lists and is more complex to implement.

Common mistakes and how to put them right

• Claiming bubble sort is faster than merge sort on large lists.

  Put it right by noting bubble sort makes many comparisons and merge sort is generally more efficient on large data.

• Saying merge sort needs no extra memory.

  Put it right by explaining that dividing into sub-lists requires additional storage.

• Describing bubble sort as splitting the list in half.

  Put it right by stating that bubble sort compares and swaps adjacent items, while merge sort does the splitting.

Exam tips

• Learn one clear advantage and one clear disadvantage for each algorithm so you can select the right one in a multiple-choice question.
• Link each advantage or disadvantage to how the algorithm actually works, such as comparisons for bubble sort and extra memory for merge sort.
• Trace a short list through both algorithms so you can recognise descriptions of their behaviour in the options.