Sorting Algorithms: Insertion Sort and Merge Sort

Sorting algorithms come alive when students physically move data rather than watch animations. Insertion sort’s step-by-step shifting and merge sort’s divide-and-conquer merging make abstract concepts concrete through hands-on sorting. Active participation helps students internalize how algorithm choices change performance with different inputs.

• Grade 11
• Computer Science
• 4 activities
• 30 min–50 min

Learning Objectives

1. Compare the time complexity of insertion sort and merge sort for various input sizes.
2. Analyze the recursive structure of merge sort and its impact on performance.
3. Explain the step-by-step process of insertion sort, including element shifting.
4. Predict the best-case and worst-case performance scenarios for insertion sort.
5. Evaluate the efficiency trade-offs between insertion sort and merge sort for different data distributions.

Problem-Based Learning

⏱ 30 min·Pairs

Card Sort Simulation: Insertion Sort

Provide shuffled number cards to pairs. Students insert one card at a time into a growing sorted hand, counting shifts aloud. Switch roles after 10 cards and discuss patterns on nearly sorted vs. random decks.

Prepare & details

Differentiate the core strategy of insertion sort from merge sort.

Facilitation Tip: During the card sort simulation, circulate and ask each pair to explain why they placed a card in a certain position, reinforcing the shift-and-insert logic.

Setup: Groups at tables with access to research materials

Materials: Problem scenario document, KWL chart or inquiry framework, Resource library, Solution presentation template

• Analyze
• Evaluate
• Create
• Decision-Making
• Self-Management
• Relationship Skills

Problem-Based Learning

⏱ 45 min·Small Groups

Divide and Merge Relay: Merge Sort

In small groups, divide a deck into halves, sort subgroups recursively, then merge by comparing top cards. Time the process and record merge steps on chart paper. Compare group times for insights on scaling.

Prepare & details

Analyze how merge sort's divide-and-conquer approach contributes to its efficiency.

Facilitation Tip: For the divide and merge relay, assign roles so every student participates in both division and merging, ensuring no one passively observes.

Setup: Groups at tables with access to research materials

Materials: Problem scenario document, KWL chart or inquiry framework, Resource library, Solution presentation template

• Analyze
• Evaluate
• Create
• Decision-Making
• Self-Management
• Relationship Skills

Problem-Based Learning

⏱ 50 min·Individual

Code and Benchmark Challenge

Individuals implement both sorts in Python, test on datasets of sizes 100, 1000, and nearly sorted arrays. Log runtimes in a shared sheet and graph results to analyze big-O empirically.

Prepare & details

Predict the performance of insertion sort on nearly sorted data.

Facilitation Tip: In the code and benchmark challenge, provide pre-labeled arrays so students focus on timing and comparisons rather than setup errors.

Setup: Groups at tables with access to research materials

Materials: Problem scenario document, KWL chart or inquiry framework, Resource library, Solution presentation template

• Analyze
• Evaluate
• Create
• Decision-Making
• Self-Management
• Relationship Skills

Problem-Based Learning

⏱ 35 min·Whole Class

Data Set Showdown: Whole Class Debate

Class generates datasets on board. Predict and vote on faster algorithm per set, then run quick simulations. Tally results to vote on best use cases.

Prepare & details

Differentiate the core strategy of insertion sort from merge sort.

Setup: Groups at tables with access to research materials

Materials: Problem scenario document, KWL chart or inquiry framework, Resource library, Solution presentation template

• Analyze
• Evaluate
• Create
• Decision-Making
• Self-Management
• Relationship Skills

Teaching This Topic

Teachers should begin with small, familiar data sets to build intuition before moving to larger arrays. Avoid rushing to code; let students manipulate physical or visual representations first to anchor abstract ideas. Research shows that drawing arrays during tracing helps students track shifts and merges more accurately than mental tracing alone.

What to Expect

Students will accurately trace the steps of each algorithm, connect runtime to input conditions, and justify choices between the two sorts based on efficiency. Clear articulation of Big O trade-offs and recursive structure will show deep understanding beyond memorized facts.

Watch Out for These Misconceptions

Common Misconception

During Card Sort Simulation: Insertion Sort, watch for students who claim insertion sort is always faster because it feels intuitive.

What to Teach Instead

Pause the activity and ask each group to time their sorting of a reverse-order deck, then plot the shift counts on the board to show how O(n^2) grows when data is out of order.

Common Misconception

During Divide and Merge Relay: Merge Sort, watch for students who assume merge sort never uses recursion.

What to Teach Instead

After the relay, have each group sketch the call stack on the board, labeling each recursive split until base cases are reached.

Common Misconception

During Code and Benchmark Challenge, watch for students who think both algorithms have the same worst-case efficiency.

What to Teach Instead

Guide students to graph their benchmark results on shared axes, highlighting how insertion’s curve steepens while merge’s remains linearithmic.

Assessment Ideas

Quick Check

After Card Sort Simulation: Insertion Sort, give students a small reverse-sorted list and ask them to trace the insertion steps on paper, labeling each comparison and shift before sharing with a partner for verification.

Discussion Prompt

During Data Set Showdown: Whole Class Debate, ask groups to present their decision on which algorithm to use for a given data set, citing Big O and their benchmark results from the Code and Benchmark Challenge.

Exit Ticket

After Merge Sort Relay, ask students to write one sentence comparing the recursive structure of merge sort to the iterative shifting in insertion sort, and predict which would handle 10,000 elements faster.

Extensions & Scaffolding

• Challenge students to optimize their insertion sort code by adding early-exit conditions for partially sorted data.
• Scaffolding: Provide partially completed trace tables for students who struggle with recording comparisons and shifts during the card sort.
• Deeper: Have students research and compare insertion sort with bubble sort, creating a Venn diagram to highlight differences in swaps versus shifts.

Key Vocabulary

Insertion Sort	A simple sorting algorithm that builds a sorted array one item at a time by taking elements from the unsorted input and inserting them into their correct position in the sorted output.
Merge Sort	A divide-and-conquer sorting algorithm that recursively divides the input array into halves, sorts each half, and then merges the sorted halves back together.
Divide and Conquer	An algorithmic paradigm that recursively breaks down a problem into smaller subproblems, solves the subproblems independently, and then combines their solutions to solve the original problem.
Time Complexity	A measure of how the runtime of an algorithm scales with the size of the input, often expressed using Big O notation.