Sorting algorithms revision notes

Bubble sort

Bubble sort repeatedly compares adjacent items in a list. If the adjacent items are in the wrong order, they are swapped. A pass moves through the list, and repeated passes progressively place items into their correct positions. It is described by the AQA specification as a particularly inefficient sorting algorithm in terms of time. Its time complexity is O(n²), where *n* is the number of items being sorted.

Worked trace

For the list [5, 2, 4], compare 5 and 2; they are in the wrong order, so swap them: [2, 5, 4]. Compare 5 and 4; swap them: [2, 4, 5]. The list is now sorted. A trace should show each comparison and every swap, rather than only the final result.

Merge sort

Merge sort uses a Divide and Conquer approach. The list is divided into smaller parts, these parts are sorted, and the sorted parts are merged to form a complete sorted list. During a merge, the next smallest available item from the divided lists is selected and placed into the result.

For [8, 3, 5, 1], divide into [8, 3] and [5, 1], then divide again into individual items. Merge [8] and [3] to produce [3, 8], and merge [5] and [1] to produce [1, 5]. Finally, merge [3, 8] and [1, 5] to produce [1, 3, 5, 8]. The time complexity of merge sort is O(n log n).

Common errors

Do not confuse the two complexities: bubble sort is O(n²), whereas merge sort is O(n log n). Do not describe merge sort as merely swapping adjacent items; its key mechanism is dividing and then merging. When tracing either algorithm, record the intermediate lists and explain why each comparison, swap, division or merge occurs.