AAlgorithm LabLesson 04

Divide and conquer, made visible

Split the problem.
Merge the answers.

Merge Sort keeps dividing an array until every piece is trivial, then combines those pieces in sorted order.

Start visualizing How it works
Mini example[ 8, 3, 6, 2 ]
01
8362
split
02
3826
halves
03
2368
merge

Key idea Two sorted halves can be merged in one linear scan by comparing only their front values.

Before you start

What you will learn

A clear finish line for the lesson, plus the small amount of knowledge you need before beginning.

Learning objectives
  1. Explain the divide, base-case, and merge phases of the recursion tree.
  2. Trace two sorted halves as they become one sorted output.
  3. Implement Merge Sort in JavaScript, Python, Java, or C++.
  4. Recognize its stable O(n log n) guarantee and O(n) auxiliary-space cost.
01Understand02Visualize03Trace04Code05Complexity06Quiz07Challenge08Use cases

01 — The idea

How Merge Sort thinks

Instead of sorting one large array directly, what if we solve two smaller versions and combine them?

1
8 3|6 2

Divide in half

Split each array near its midpoint until only single values remain.

2
3826

Trust the small answers

A one-value array is already sorted, so recursion has a base case.

3
236

Merge in order

Compare the fronts of two sorted halves and take the smaller value.

02 — Try it yourself

Watch the recursion tree resolve

Follow each split from root to base case, then compare both fronts as sorted halves merge upward.

3–8 values, each from 1 to 99
Depth 0 Paused
Left half
Empty
Right half
Empty
Temporary output
Empty
→

Ready. Begin by dividing the full array near its midpoint.

Comparisons0
Writes0
Merges0
Active call Current fronts Resolved
Dry-run trace

Turn each animation into a written decision

The latest eight Merge Sort decisions
StepPassActionCurrent frontsCurrent outputWrites
0—Ready—[38, 27, 43, 3, 9, 82, 10, 15]0

The highlighted row always matches the visualization above. Step forward to extend the trace.

03 — Read the code

From recursive halves to working code

Compare the same base case, recursive split, and stable left-first merge across all four languages.

merge-sort.mjs
01function mergeSort(numbers) {02  if (numbers.length <= 1) return [...numbers];03  const middle = Math.floor(numbers.length / 2);04  const left = mergeSort(numbers.slice(0, middle));05  const right = mergeSort(numbers.slice(middle));06  return merge(left, right);07}08 09function merge(left, right) {10  const output = [];11  let leftIndex = 0;12  let rightIndex = 0;13  while (leftIndex < left.length && rightIndex < right.length) {14    if (left[leftIndex] <= right[rightIndex]) {15      output.push(left[leftIndex++]);16    } else {17      output.push(right[rightIndex++]);18    }19  }20  return output.concat(left.slice(leftIndex), right.slice(rightIndex));21}

04 — Avoid the traps

Common mistakes

These bugs often produce an answer that looks almost right. Learn the symptom and the correction together.

01

Missing the base case

Symptom: The recursive calls continue forever or fail on empty arrays.

Correction: Return a copy immediately when the array has zero or one value.

02

Dropping remaining values

Symptom: The merged output is shorter than the two inputs combined.

Correction: After one half is exhausted, append every value still waiting in the other half.

03

Taking from the right on ties

Symptom: Equal values reverse their original order.

Correction: Use ≤ and take the left value first when both fronts are equal.

04

Re-sorting during merge

Symptom: The merge step uses another sorting function or scans the full output repeatedly.

Correction: Rely on both halves already being sorted and advance one front pointer at a time.

05 — Check yourself

Check your understanding

Answer 4 questions, then reveal the reasoning. Your progress stays on this device—no account required.

0 of 4 answered
Q1Why does recursion stop at an array of length one?
Q2When merging [2, 6] and [3, 5], which value is taken first?
Q3What is Merge Sort's worst-case time complexity?
Q4How does the merge step preserve stability when front values are equal?

Answer every question to check your work.

06 — Mini game

Merge two sorted queues

Build one sorted output by repeatedly choosing the smaller front value.

Rule Only the front card of each queue is available. On equal values, choose the left queue first.
Choose the smaller front0 picks
left queue
right queue
Merged output
↓

Compare only the two available front cards.

07 — Use it wisely

Where Merge Sort fits

∞

Predictable performance

O(n log n) time is guaranteed regardless of the input's original order.

Great fit
≡

External sorting

Sequential merging works well when large datasets live on disk instead of memory.

Excellent fit
⑂

Linked lists and parallel work

Halves can be processed independently, and linked lists merge without shifting values.

Good fit
×

Tiny memory-limited arrays

Temporary merge storage and recursive overhead may outweigh its benefits.

Consider another sort

Lesson progress

Finish this lesson with confidence

Use this private checklist to confirm what you learned. Progress stays only in this browser.

0 of 4 complete0%

Complete every checklist item to finish the lesson.