1. Concept library
  2. Data Structures & Algorithms
  3. Module 7: Sorting

Concept

Merge sort

Merge sort splits the array in half, sorts each half, and merges the two sorted halves. It is O(n log n) in every case and stable, at the cost of O(n) extra memory.

What a session covers

The tutor works through these with you, in conversation and code. A session ends when you have shown them, not when a video does.

  1. Explain the split, sort and merge steps and why the result is O(n log n)
  2. Write the merge step and trace it on two short sorted lists
  3. Spot the < that breaks stability and fix it

In practice

A few lines that show Merge sort doing its job.

Python
def merge_sort(a):
    if len(a) <= 1:
        return a
    mid = len(a) // 2
    left, right = merge_sort(a[:mid]), merge_sort(a[mid:])
    merged, i, j = [], 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            merged.append(left[i]); i += 1
        else:
            merged.append(right[j]); j += 1
    return merged + left[i:] + right[j:]

The common mistake

Watch for

Using < instead of <= when merging. Equal elements from the right half then come before those from the left, and the sort is no longer stable.

What to know first

Your roadmap puts these before Merge sort, unless you already know them.

How it stays learned

Once a session shows you understand Merge sort, it comes back for review. Each review takes a minute and tells the memory model how well you still know it.

  1. Day 3First recall, while it is fresh
  2. Day 7Second, a week on
  3. Day 18Last, when it has settled

Where it leads

Topics that build on Merge sort.

Next in the moduleQuicksort →