Worksheet

F5.9 Merge sort and comparing algorithms

Algorithms · GCSE · OCR J277 2.1.3, AQA 8525 3.1.2, Edexcel 1CP2 1.2.7 · about 20 min

What this lesson is about

Splitting and merging, and choosing between the searches and sorts.

• Merging two sorted lists
• Splitting and merging
• Comparing the sorts
• Choosing an algorithm

Questions 5 marks in all

1. [1 mark]What does this program print?

   left, right = [2, 8], [3, 4, 20]
   result = []
   i = j = 0
   while i < len(left) and j < len(right):
       if left[i] <= right[j]:
           result.append(left[i]); i = i + 1
       else:
           result.append(right[j]); j = j + 1
   print(result + left[i:] + right[j:])

2. [1 mark]Put the stages of merge sort in order.

   Number the lines 1 to 4 to put them in the right order.

   1. Keep splitting until every part has one item
   2. Merge pairs of parts into sorted parts
   3. Keep merging until one sorted list is left
   4. Split the list in half

3. [1 mark]Why is merge sort usually faster than bubble sort on large lists?

   1. AIt needs far fewer comparisons as the list grows
   2. BIt uses no memory
   3. CIt only works on sorted lists
   4. DIt skips half the items

4. [1 mark]What is a disadvantage of merge sort compared with bubble sort?

   1. AIt uses more memory, building new lists as it merges
   2. BIt is slower on large lists
   3. CIt cannot sort numbers
   4. DIt needs the list already sorted

5. [1 mark]A school has 2 million sorted records and searches them thousands of times a day. Which search should it use?

   1. ABinary search
   2. BLinear search
   3. CBubble sort
   4. DInsertion sort

The task: merge two tunes

Two robots each played a sorted tune: left = [262, 330, 440, 523] and right = [294, 349, 392, 494]. Write merge(left, right) yourself (no sort or sorted) and use it to make one sorted tune. Print merged: <the list> and play every note for 0.2 seconds.

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

left = [262, 330, 440, 523]
right = [294, 349, 392, 494]

Plan your program here, then type it in and press Run.

Do it on the robot
www.bugbotlab.com/learn/f5-9-merge-sort-and-comparing/
The simulator checks it and tells you when it passes. Nothing to install, no account.

Challenges

1. Add a comparison count to merge, and check it is never more than the total number of items.
2. Run the comparison cell with a list that is already sorted. Which algorithm wins now, and why?
3. Write the split and merge diagram for [6, 5, 3, 1, 8, 7, 2, 4] by hand, then check it with merge_sort.