Case Study • Algorithms

Merge Sort

A structured learning module for recursive splitting, base-case recognition, and ordered merging.

Merge sort can feel abstract because learners often see only the unsorted array and the final sorted answer, without clearly seeing what happens in between. This module turns recursion into a visible sequence of splits and merges so learners can follow how the array is repeatedly divided, then rebuilt in sorted order.

The lesson focuses on the mental model learners need most: keep splitting until each sublist has one item, then merge back by comparing the two front values and copying the smaller one first.

Watch Demo

Project Scope

Curricular Target

Introductory Algorithms or Data Structures courses introducing divide-and-conquer thinking.

Delivery Model

Hybrid instructional module; adaptable for lecture, guided practice, or asynchronous review.

Learner Profile

Students transitioning from iterative sorting methods to recursive reasoning and multi-stage state tracking.

Primary Objective

Enable learners to explain how recursive splitting and ordered merging work together to produce a sorted array.

Core Learning Outcomes

Explain divide-and-conquer as a split-then-merge process.
Trace recursive array partitioning until base cases are reached.
Apply the merge rule by comparing the two front values and copying the smaller one first.
Predict intermediate sorted sublists and final merge outcomes.

Learning Challenge

Learners often struggle with merge sort because recursion hides the intermediate states. Without a clear visual sequence, the algorithm appears to jump from an unsorted array to a sorted result. A second challenge is understanding the merge phase itself: students may not know which two values should be compared next or why the remaining values are copied over when one side becomes empty.

Design Strategy

Split and Merge as Separate Phases

The lesson treats recursive decomposition and ordered merging as two distinct stages so learners do not have to process both ideas at once.

Base Cases Made Visible

Single-item sublists are explicitly shown as stopping points, helping learners understand when recursion ends.

Compare-the-Front Rule

During merging, the animation highlights the two current front values so learners can focus on one decision at a time.

Copy-the-Rest Rule

When one side becomes empty, the lesson explicitly shows why the remaining values are copied over in order.

Solution Design

The learning sequence is structured to make recursion visible and predictable by turning each split and merge into an observable structural event.

1. Concrete Array Before Abstraction

The lesson begins with the full array [9, 4, 7, 1, 6, 2, 8, 5, 3], giving learners a stable starting state before any recursive split occurs.

2. Recursive Splitting as Visible Structure

The array is split into left and right halves repeatedly, creating a visible recursion tree rather than leaving the process hidden inside function calls.

3. Base Cases as Stopping Conditions

Single-item segments are treated as important cognitive anchors. Learners can see that once a segment has one item, it is already sorted and ready for merging.

4. Merge Steps as Ordered Comparisons

Merging is slowed into explicit comparisons such as 9 vs 4, 5 vs 3, and 2 vs 3, helping learners understand why values leave their sublists in a specific order.

5. Reconstruction as a Pattern

Sorted segments merge upward in a consistent pattern until the full array is rebuilt in order, reinforcing merge sort as a reusable divide-and-conquer system.

Design Refinement:

Early learner confusion centered on two moments: recognizing when the split phase should stop, and knowing what to do when one side of a merge becomes empty.

To address this, the base case was emphasized visually, merge comparisons were slowed, and “one side is empty → copy the rest in order” was repeated as an explicit rule throughout the animation.

Interactive Implementation

The animation reveals recursive splitting and controlled merging in slow, observable stages.

Watch actively: pause, predict the next split or comparison, and decide which value should be copied next.

This implementation uses the array [9, 4, 7, 1, 6, 2, 8, 5, 3] to show recursive decomposition, base cases, intermediate sorted segments, and the final reconstruction into [1, 2, 3, 4, 5, 6, 7, 8, 9].

Guided Worksheet (Pause & Predict)

These worksheet prompts follow the same sequence shown in the animation. Pause at each major change, predict what will happen next, then continue to confirm or revise your reasoning.

Part 1 — Read the Initial Array

What is the full unsorted array shown at the beginning?
What is the main rule of merge sort before any comparisons begin?
Why do we split the array before trying to sort it directly?
What does it mean for a sublist to be a base case?

Part 2 — First Major Split

How is the array divided into left and right halves at the first split?
Which values belong to the left side?
Which values belong to the right side?
Why is it useful to keep the left and right halves visually separate?

Part 3 — Splitting the Left Side

How is the left half [9, 4, 7, 1, 6] split next?
Which segment becomes [9, 4, 7]?
Which segment becomes [1, 6]?
At what point does a segment become small enough to stop splitting?

Part 4 — Merging [9] and [4]

When comparing 9 and 4, which value should be copied first?
Why is 4 copied before 9?
What sorted segment is produced after this merge?
What rule is used once one side becomes empty?

Part 5 — Merging [4, 9] with [7]

When comparing 4 and 7, which value is copied first?
After copying 4, what comparison happens next?
Why is 7 copied before 9?
What final sorted segment is formed from [9, 4, 7]?

Part 6 — Merging [1] and [6]

When comparing 1 and 6, which value is smaller?
What sorted segment is produced after merging these two singletons?
Why is this merge simpler than merging longer segments?
How does this segment help complete the left half?

Part 7 — Completing the Left Half

Which two sorted segments are merged to form the full left side?
When comparing 4 and 1, which value is copied first?
When comparing 7 and 6, which value is copied first?
What fully sorted left half is produced?

Part 8 — Splitting and Merging the Right Half

How is the right half [2, 8, 5, 3] divided?
Which pair forms the segment [2, 8]?
When comparing 5 and 3, which value is copied first?
What sorted segment is produced from [5, 3]?

Part 9 — Completing the Right Half

Which two sorted segments are merged to form the full right side?
When comparing 2 and 3, which value is copied first?
When comparing 8 and 5, which value is copied first?
What fully sorted right half is produced?

Part 10 — Final Merge

Which two sorted halves are merged at the final step?
When comparing 1 and 2, which value is copied first?
Later in the merge, why is 5 copied before 6?
After one side becomes empty, what should happen to the remaining values?
What final sorted array is produced?

Part 11 — Reflection

Which merge step felt easiest to predict, and why?
Which step best helped you understand the “copy the rest” rule?
Why is merge sort easier to follow when splitting and merging are shown separately?
How does this process differ from sorting methods that repeatedly swap nearby values?

Focus on the structure of the process: split until each segment has one item, then merge back by comparing the two current front values and copying the smaller one first.

Assessment Strategy

This module evaluates understanding through guided prediction, split-tree reasoning, and ordered merge interpretation.

Formative assessment (during learning): Students predict the next split or next copied value during a merge.
- Which segment should be split next?
- Has this segment reached a base case yet?
- Which two values are being compared right now?
- Which value should be copied next, and why?
Application assessment (structure + merge reasoning): Students explain how intermediate sorted segments are produced and used in later merges.
- What sorted segment is formed from this merge?
- Why is this segment already sorted before moving upward?
- What happens when one side becomes empty?
- How does this segment contribute to a larger merge later?
Summative assessment (after learning): A short exit check confirms whether students can explain both the divide phase and the merge phase.
- Why does merge sort keep splitting until each sublist has one item?
- How does the merge step preserve sorted order?
- Why can the remaining values be copied directly when one side is empty?
- How does merge sort combine recursion with comparison-based sorting?

Assessment Activities

Prediction prompts before each split and merge step.
Segment reconstruction from intermediate merge results.
Compare-the-front checks during ordered merging.
Base-case and copy-the-rest questions using the actual array sequence.

Inclusive Design

Left/right labels reduce confusion during recursive splitting.
Explicit merge comparisons support learners who need slower reasoning tempo.
Pacing control supports repeated review of split and merge phases.
Guided worksheet prompts support different learning preferences.

Instructional Impact

The module helps learners move from seeing merge sort as a hidden recursive trick to understanding it as a visible divide-and-conquer process with clear base cases, ordered comparisons, and predictable reconstruction.