Computing · Secondary 4

Active learning ideas

Advanced Sorting Algorithms: Merge Sort

Active learning helps students grasp divide-and-conquer logic more deeply than passive lectures for merge sort. Handling physical cards or tracing recursive trees makes the invisible process of splitting and merging tangible for learners.

• MOE Syllabus Outcomes
• MOE: Algorithms - S4
• MOE: Computational Thinking - S4

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

Activity 01

• Concept Mapping
• 35 min · Small Groups

Card Sort: Physical Merge Sort

Distribute shuffled number cards to small groups. Students recursively divide piles, sort singles, and merge by comparing top cards, recording steps on worksheets. Groups present one merge to the class for feedback.

Differentiate between iterative and recursive approaches in sorting algorithms.

Facilitation Tip

In Efficiency Race, set identical random arrays for each pair to prevent skewed comparisons and prompt discussion of input size impacts.

What to look for

Provide students with a small, unsorted array (e.g., [5, 2, 8, 1, 9]). Ask them to manually trace the first two levels of recursion for merge sort, showing how the array is split and the initial merge steps. They should write down the state of the array after each merge.

• Understand
• Analyze
• Create
• Self-Awareness
• Self-Management

Activity 02

• Concept Mapping
• 30 min · Pairs

Recursion Trace: Tree Building

Provide sample arrays on handouts. In pairs, students draw recursion trees showing splits and merges, annotating comparisons. Pairs swap traces to verify and discuss depth.

Analyze the advantages of merge sort over simpler sorting methods.

What to look for

Pose the question: 'When might merge sort be a better choice than insertion sort for sorting a list of student scores, and why?' Encourage students to discuss time complexity, input size, and the concept of stability in their answers.

• Understand
• Analyze
• Create
• Self-Awareness
• Self-Management

Activity 03

• Concept Mapping
• 45 min · Pairs

Pair Code: Merge Sort Implementation

Pairs write merge sort in Python, testing on varied arrays. They add print statements to log recursive calls, then remove for clean code. Share timings versus bubble sort.

Construct a visual representation of merge sort's execution on a sample array.

What to look for

On an exit ticket, have students write down the base case for the merge sort recursive function and explain in one sentence why it is necessary. Then, ask them to identify one advantage of merge sort over a simple iterative sort.

• Understand
• Analyze
• Create
• Self-Awareness
• Self-Management

Activity 04

• Concept Mapping
• 40 min · Whole Class

Efficiency Race: Sort Comparisons

Whole class generates large random arrays. Students time merge sort against insertion sort using code timers, plotting results. Discuss when each excels.

Differentiate between iterative and recursive approaches in sorting algorithms.

What to look for

Provide students with a small, unsorted array (e.g., [5, 2, 8, 1, 9]). Ask them to manually trace the first two levels of recursion for merge sort, showing how the array is split and the initial merge steps. They should write down the state of the array after each merge.

• Understand
• Analyze
• Create
• Self-Awareness
• Self-Management

A few notes on teaching this unit

Teach this topic by letting students experience the cost and benefit of recursion firsthand. Avoid rushing to the final code; instead, use tracing activities to build intuition for why merge sort guarantees O(n log n) time. Research shows that visualizing splits and merges reduces misconceptions about recursion depth or infinite loops.

Students will accurately trace recursive splits, merge sorted halves without skipping comparisons, and justify merge sort’s efficiency over simpler sorts. They should articulate why recursion terminates and how merging maintains stability.

---

Watch Out for These Misconceptions

• During Card Sort, watch for students who assume subarrays are sorted without comparing elements during the merge step.

  Ask them to verbally explain each comparison as they merge pairs, using the physical cards to demonstrate why values must be checked and placed in order.

• During Recursion Trace, watch for students who believe recursion could loop infinitely because they see repeated calls.

  Have them count the depth of the tree and compare it to the array size, then discuss why halving the array each time limits recursion depth to log n.

• During Pair Code, watch for students who implement merging as simple concatenation instead of interleaving based on values.

  Ask them to trace the merge step with a small array on paper, highlighting how values are selected based on comparison, and adjust their code accordingly.

---

Methods used in this brief

• Concept Mapping