Merge sort and comparing algorithms

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

F5.9AlgorithmsGCSE20 min

Do this lesson in the simulator

Bubble sort and insertion sort are simple but slow on big lists. Merge sort uses a cleverer idea: split the list into tiny pieces that are trivially sorted, then merge sorted pieces together, again and again, until one sorted list is left. It is much faster on big lists, and the idea behind it, divide and conquer, is one of the most important in computing. This lesson also compares all the algorithms in the module.

Merging two sorted lists

The key step is merging. Given two lists that are already sorted, you only ever need to compare their front items:

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

def merge(left, right):
    """Merge two sorted lists into one sorted list."""
    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
    result = result + left[i:] + right[j:]      # whatever is left over is already in order
    return result

print(merge([2, 8, 15], [3, 4, 20, 25]))

Run this in the simulator

Each comparison moves exactly one item into the result, so merging two lists takes at most as many comparisons as there are items. When one list runs out, the rest of the other goes on the end, in order.

Splitting and merging

Merge sort splits the list in half, and each half in half again, until every piece has one item. A list of one is sorted. Then it merges the pieces back together in pairs:

split:   [38, 27, 43, 3, 9, 82, 10]
         [38, 27, 43]           [3, 9, 82, 10]
         [38] [27, 43]          [3, 9] [82, 10]
         [38] [27] [43]         [3] [9] [82] [10]
merge:   [38] [27, 43]          [3, 9] [10, 82]
         [27, 38, 43]           [3, 9, 10, 82]
         [3, 9, 10, 27, 38, 43, 82]

In Python, the neatest way to write "sort each half the same way" is a function that calls itself, which is called recursion:

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

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

def merge_sort(items):
    if len(items) <= 1:
        return items                       # a list of one is already sorted
    middle = len(items) // 2
    left = merge_sort(items[:middle])      # sort each half the same way
    right = merge_sort(items[middle:])
    return merge(left, right)

print(merge_sort([38, 27, 43, 3, 9, 82, 10]))

Run this in the simulator

You do not need to write recursion for GCSE, but you do need to describe merge sort's split and merge steps and show them on a list, as in the diagram above.

Comparing the sorts

Count the comparisons each sort makes on the same list:

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

import random

def bubble_count(items):
    items, count, swapped = list(items), 0, True
    while swapped:
        swapped = False
        for i in range(len(items) - 1):
            count = count + 1
            if items[i] > items[i + 1]:
                items[i], items[i + 1] = items[i + 1], items[i]
                swapped = True
    return count

def merge_count(items):
    if len(items) <= 1:
        return items, 0
    mid = len(items) // 2
    left, a = merge_count(items[:mid])
    right, b = merge_count(items[mid:])
    result, i, j, c = [], 0, 0, 0
    while i < len(left) and j < len(right):
        c = c + 1
        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:], a + b + c

for n in [10, 100, 250]:
    data = [random.randint(1, 1000) for _ in range(n)]
    print(n, "items: bubble", bubble_count(data), "comparisons, merge", merge_count(data)[1])

Run this in the simulator

For 250 items, bubble sort makes tens of thousands of comparisons and merge sort under two thousand. The gap grows as the list grows. The price merge sort pays is memory: it builds new lists as it merges, where bubble sort works inside the one list it was given.

Choosing an algorithm

Algorithm Needs sorted data? Speed on big lists Extra memory Good for
Linear search no slow none short or unsorted lists
Binary search yes very fast none big sorted lists
Bubble sort slow none short or nearly sorted lists; teaching
Insertion sort slow, but quick if nearly sorted none adding a few items to a sorted list
Merge sort fast more big lists

There is no single best algorithm. The right one depends on how much data there is, whether it is sorted, how often it changes, and how much memory the computer has. Choosing well is called judging an algorithm's fitness for purpose.

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]

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.