Skip to content

Merge Sort

Your card-sorting algorithm worked one card at a time. Merge sort refuses to sort anything at all — it just splits the list in half, hands each half to another copy of itself, and lets a one-item list count as sorted. That sounds like dodging the work. It's actually one of the fastest sorting algorithms ever devised, and after the Mondrian lab, you already know its secret: it's recursion.

Overview

Concept: Break the list into smaller pieces, sort those pieces, then combine them back together in order.

  1. Divide: Recursively split the unsorted list into two halves until each sublist contains only one element.
  2. Conquer: A single-element list is considered sorted.
  3. Combine (Merge): Repeatedly merge the sorted sublists back together to produce new sorted sublists until only one remains.

A list of numbers split down to single elements, then merged back together in sorted order.

Builds on: Recursion — the same split-and-recurse pattern that painted Mondrians, now sorting lists.

You've got it when…

  • Your merge function combines two sorted lists into one sorted list.
  • Your merge_sort function sorts any list by calling itself, then calling merge.
  • You've tested both functions — including odd-length lists, an empty list, and a list of one item.

Collaboration & AI

Work: On your own. Compare test results with a neighbor, not code.

AI — AIAS Level 1, No AI: Implementing an algorithm from its description is the whole assignment. Follow the steps below yourself. What the levels mean.

The Algorithm

Part 1: The Merge Sort Process

  1. If the list has one item or fewer, it is already sorted — return the list.
  2. Find the middle of the list.
  3. Split the list into two halves: a left half and a right half.
  4. Sort the left half using merge sort.
  5. Sort the right half using merge sort.
  6. Merge the two sorted halves back together (see Part 2 below).
  7. Return the merged list.

Steps 4 and 5 are the recursion

"Sort the left half using merge sort" — the algorithm you are writing calls itself, just like subdivide did. Step 1 is its stopping condition, and it's why the whole thing ends: every split eventually produces lists of one item, and those come back immediately.

Part 2: How to Merge Two Sorted Lists

You are given two already sorted lists (left and right).

  1. Create an empty list called result.
  2. Set two positions: i for the left list and j for the right list, both starting at 0.
  3. Repeat while both lists still have items left:
    1. Compare the current items, left[i] and right[j].
    2. If left[i] is smaller: add it to result and move i forward.
    3. Otherwise: add right[j] to result and move j forward.
  4. If there are remaining items in the left list, add all of them to result.
  5. If there are remaining items in the right list, add all of them to result.
  6. Return result.

Why merging is the easy part

Both lists arrive sorted, so the smallest unclaimed item is always sitting at the front of one list or the other. Merging never searches — it just compares the two front items and takes the smaller one, like two checkout lines feeding one door.

Task

Implement the merge sort algorithm in Python.

How to tackle this? Tips:

  1. Write the merge part first (Part 2 above).

    Start with a function that accepts two lists, left and right:

    def merge(left, right):
    • This function should return a new list with the two lists merged in sorted order.
    • Follow the steps in Part 2 of the algorithm above to write this function.

  2. Test your merge function with small lists.

    What does a good merge test look like?

    Feed it two short sorted lists by hand — say [2, 5, 9] and [1, 5, 6] — and check the output against what you'd expect. Then try uneven lengths and an empty list on one side.

  3. Now write a merge sort function (Part 1 above).

    This function accepts a list of items to sort:

    def merge_sort(input_list):
    • This function will call your merge function.
    • Follow the steps in Part 1 of the algorithm above to write this function.

Warning

Merge sort functions return their results — merge_sort hands back a new sorted list rather than rearranging the one you gave it. Forgetting a return (in steps 1 or 7 of Part 1, or step 6 of Part 2) is the most common way this lab produces a program that runs fine and sorts nothing.

Turn It In

  • Your Python (.py) file with your merge and merge_sort functions.

How It's Graded

This lab is worth up to 4 points. One score covers everything you turn in.

Score What it looks like
4 — Excellent merge combines two sorted lists correctly and merge_sort sorts by calling itself and then merge — both return their results — and your file shows the tests that prove it, including odd-length lists, an empty list, and a list of one.
3 — Above Average Both functions work; an edge case went untested, or a test that exists in your head but not in the file.
2 — Average merge works but merge_sort doesn't — usually a missing return, the bug that runs fine and sorts nothing.
1 — Below Average Neither function produces sorted output.
0 — Failing No file turned in.