Computer Science · Grade 12

Active learning ideas

Sorting Algorithms: Advanced (MergeSort)

MergeSort’s abstract steps can overwhelm students if they only read or watch. Active learning through simulations and coding lets them feel the divide-and-conquer rhythm, turning recursive calls into visible card stacks and merge steps into ordered piles. This physical and digital engagement builds the intuition needed to trust the O(n log n) guarantee across all input types.

• Ontario Curriculum Expectations
• CS.AA.8
• CS.P.18

• 45–90 min
• Pairs → Whole Class
• 3 activities

Activity 01

• Inquiry Circle
• 60 min · Individual

MergeSort Visualization: Step-by-Step Debugging

Students use an online MergeSort visualizer to trace the algorithm's execution on various input arrays. They then manually step through the code, identifying and correcting logical errors in a provided, partially implemented MergeSort function.

Which sorting algorithm provides the best performance for nearly sorted data?

Facilitation Tip

During the Card Simulation, circulate and ask each pair to explain the merge step out loud as they place cards in order, ensuring every student verbalizes the comparison logic.

• Analyze
• Evaluate
• Create
• Self-Management
• Self-Awareness

Activity 02

• Inquiry Circle
• 90 min · Small Groups

Algorithm Performance Comparison: Benchmarking

In small groups, students implement MergeSort and at least two other sorting algorithms (e.g., Bubble Sort, QuickSort). They then design and run experiments to measure the execution time of each algorithm on datasets of varying sizes and characteristics, analyzing the results.

Explain how MergeSort achieves its O(n log n) time complexity.

Facilitation Tip

When students Pair Program MergeSort, require them to add print statements after each recursive call and merge to trace the recursion depth and merge order in real time.

• Analyze
• Evaluate
• Create
• Self-Management
• Self-Awareness

Activity 03

• Inquiry Circle
• 45 min · Pairs

MergeSort Debugging Challenge

Provide students with a buggy MergeSort implementation. Working in pairs, they must identify the errors, explain why they occur, and then fix the code to correctly sort the array.

Analyze the spatial costs of recursive sorting algorithms compared to iterative ones.

Facilitation Tip

For the Visualization Trace, provide colored pens so students can annotate each merge level with the number of comparisons and swaps, making complexity visible on paper.

• Analyze
• Evaluate
• Create
• Self-Management
• Self-Awareness

A few notes on teaching this unit

Start with the Card Simulation to ground recursion in a physical model, then move to code so students see how their hand movements translate to function calls. Avoid rushing to the formula; instead, have them solve small recurrences by counting actual splits and merges. Research shows this concrete-to-abstract path builds retention, while premature abstraction leads to fragile understanding.

By the end of these activities, students will articulate how MergeSort splits and merges, trace its recursion tree, and justify its space and time complexity with concrete examples. They will also compare it to other sorts without relying on memorized claims.

---

Watch Out for These Misconceptions

• During Card Simulation: MergeSort, watch for students who believe the recursion stack uses O(n^2) space because many cards are shuffled around.

  Point to the temporary holding piles and ask them to count how many cards are held in total at any merge level—this concrete count will show O(n) auxiliary space.

• During Pair Programming: Code MergeSort, watch for students who assume MergeSort runs slowly on nearly sorted data.

  Have them time three arrays: random, nearly sorted, and reverse sorted, then compare runtimes; the consistent O(n log n) will challenge their assumption.

• During Visualization Trace: Complexity Analysis, watch for students who credit only the merge step for the O(n log n) runtime.

  Pause tracing and ask them to count both the number of splits (log n) and the cost per merge (n) on their annotated diagram.

---

Methods used in this brief

• Inquiry Circle