Merge sort

Overview

Recall questions on the divide and merge phases of merge sort, merging two sorted lists, tracing a merge sort, why it is O(n log n) in every case, levels of splitting, space complexity, stability, external sorting, and when to choose it.

What you need to know

Answer each one before you reveal it.

Questions from this subtopic

Each one with the model answer underneath.

1. 1

   Describe the two distinct phases of a merge sort.

   Model answer

   First the divide phase: the list is split in half, and each half is split in half again, repeatedly, until every piece contains a single item. A list of one item is trivially sorted. Then the merge phase: pairs of sorted pieces are combined into single sorted pieces, repeatedly, until one sorted list of the original size remains. The dividing does no comparing and the merging does all of it.

2. 2

   Explain exactly how two already-sorted lists are merged.

   Model answer

   Look at the first item of each list. Take whichever is smaller, add it to the output and move that list's pointer on by one. Repeat, always comparing the two current front items. When one list runs out, everything left in the other is already in order and is copied straight onto the end of the output.

3. 3

   Merge the sorted lists 2, 5, 9 and 1, 6 by hand, showing each comparison.

   Model answer

   Compare 2 and 1: take 1. Compare 2 and 6: take 2. Compare 5 and 6: take 5. Compare 9 and 6: take 6. The second list is now empty, so 9 is copied across. The merged list is 1, 2, 5, 6, 9, produced in four comparisons.

4. 4

   Trace a merge sort on the list 6, 3, 8, 1.

   Model answer

   Divide into 6, 3 and 8, 1, then divide again into the single items 6, 3, 8 and 1. Merge 6 and 3: 3 is smaller, giving 3, 6. Merge 8 and 1: 1 is smaller, giving 1, 8. Now merge 3, 6 with 1, 8: compare 3 and 1, take 1; compare 3 and 8, take 3; compare 6 and 8, take 6; the first list is empty so 8 follows. The result is 1, 3, 6, 8.

5. 5

   Why is merge sort O(n log n) in every case?

   Model answer

   Halving the list repeatedly until pieces of one item remain takes log n levels of division. At each level of merging, every one of the n items is looked at and copied exactly once, costing O(n). Multiplying the number of levels by the cost per level gives O(n log n), and neither figure depends on how the data happened to be arranged.

6. 6

   How many levels of splitting does a merge sort of 8 items need, and what does that tell you?

   Model answer

   Three: 8 becomes two 4s, then four 2s, then eight 1s. That is log to base 2 of 8, which is 3. Doubling the list to 16 items would add just one more level, which is why the log n factor grows so slowly.

Other ways to work this

The same content, four other ways.

What is inside Levo

Six ways to work the same material.