Answers

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:])

   Answer:

   [2, 3, 4, 8, 20]

   Merging compares only the front items, then adds what is left over.

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
   Answer:

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

   Divide first, then conquer by merging.

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
   Answer: A. Bubble sort's comparisons grow with n times n; merge sort's grow much more slowly.

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
   Answer: A. Bubble sort works inside the original list; merge sort needs extra space.

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
   Answer: A. The data is sorted and large, and searched often: binary search's speed wins.

The task: merge two tunes

# 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]

from bugbot import *
connect()
left = [262, 330, 440, 523]
right = [294, 349, 392, 494]

def merge(left, right):
    result = []
    i = 0
    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
    return result + left[i:] + right[j:]

tune = merge(left, right)
print("merged:", tune)
for note in tune:
    tone(note, 0.2)