Merge Sort Basics — Split Lists and Merge

Merge sort basics mean mastering split, base case, and linear merge—before worrying about in-place variants or galloping heuristics.

Why this shows up in the real world

Intro CS labs everywhere use merge sort to teach recursion trees. Whiteboard interviews still ask “implement merge” because it tests index discipline without pointer tricks. Once basics are solid, optimizations like bottom-up merge sort become approachable.

Core idea (explained for students)

Split until singletons; merging two size-1 lists is trivial. Build up: sizes double each level—visualize a binary tree of subproblems. Total work per level is O(n) across all merges; there are O(log n) levels.

Try this in Python

def merge(a, b):
    out, i, j = [], 0, 0
    while i < len(a) and j < len(b):
        if a[i] <= b[j]:
            out.append(a[i])
            i += 1
        else:
            out.append(b[j])
            j += 1
    return out + a[i:] + b[j:]


print(merge([1, 3, 5], [2, 4, 6]))

Common mistakes

• Returning new lists without slicing discipline—memory blowups.
• Forgetting base case len<=1.
• Merge loop missing tail append.

Key takeaways

• Draw the recursion tree once on paper.
• Merge is the reusable core—practice standalone.
• Relate to Master theorem case 2.