Computer Science · Grade 11

Active learning ideas

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.

• Ontario Curriculum Expectations
• CS.HS.A.3
• CS.HS.A.4

• 30–50 min
• Pairs → Whole Class
• 4 activities

Activity 01

• 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.

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.

What to look for

Provide students with a small, unsorted list of numbers (e.g., 5-7 elements). Ask them to trace the execution of insertion sort on paper, showing the state of the list after each insertion. Then, ask them to identify the number of comparisons and shifts made.

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

Activity 02

• 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.

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.

What to look for

Pose the question: 'When would you choose insertion sort over merge sort, and why?' Facilitate a class discussion where students justify their choices based on input data characteristics and efficiency considerations, referencing Big O notation.

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

Activity 03

• 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.

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.

What to look for

On an exit ticket, ask students to write one sentence explaining the core difference in strategy between insertion sort and merge sort. Then, ask them to identify which algorithm they predict would perform better on an array that is already sorted in ascending order and briefly explain why.

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

Activity 04

• 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.

Differentiate the core strategy of insertion sort from merge sort.

What to look for

Provide students with a small, unsorted list of numbers (e.g., 5-7 elements). Ask them to trace the execution of insertion sort on paper, showing the state of the list after each insertion. Then, ask them to identify the number of comparisons and shifts made.

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

A few notes on teaching this unit

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.

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

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

  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.

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

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

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

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

---

Methods used in this brief

• Problem-Based Learning