Computing · Year 11

Active learning ideas

Sorting Algorithms: Merge Sort and Quick Sort

Active learning helps students grasp sorting algorithms because the divide-and-conquer process is abstract until they physically or visually manipulate data. Working with cards or code makes recursion and partitioning concrete, reducing confusion about how splits and merges actually happen.

• National Curriculum Attainment Targets
• GCSE: Computing - Algorithms
• GCSE: Computing - Computational Thinking

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

Activity 01

• Jigsaw
• 35 min · Small Groups

Card Simulation: Merge Sort Steps

Provide shuffled card decks to small groups. Students divide piles recursively, sort singles, merge while maintaining order, and count merge steps. Groups present their process on posters, noting stability with duplicate values.

Compare the recursive nature of Merge Sort and Quick Sort.

Facilitation Tip

During Card Simulation: Merge Sort Steps, have students swap roles every two merges to keep everyone engaged and accountable for explaining the merge logic aloud.

What to look for

Present students with a small unsorted array (e.g., [5, 2, 8, 1, 9]). Ask them to trace the first step of Quick Sort, explaining their pivot choice and showing the resulting partitioned array. Then, ask them to trace the first merge step of Merge Sort on a similar small array, showing the two sorted sub-arrays and the result of their merge.

• Understand
• Analyze
• Evaluate
• Relationship Skills
• Self-Management

Activity 02

• Jigsaw
• 45 min · Pairs

Pair Coding: Quick Sort Implementation

Pairs write Quick Sort in Python or pseudocode, incorporating random pivot selection. Test on varied arrays like sorted or reverse-sorted data, timing runs and discussing worst-case triggers. Share code via projector for class feedback.

Evaluate the practical implications of Quick Sort's worst-case performance.

Facilitation Tip

Before Pair Coding: Quick Sort Implementation, provide a scaffolded function signature with comments for each partition step to prevent syntax paralysis.

What to look for

Pose the question: 'When might the O(n^2) worst-case performance of Quick Sort be a significant problem, and what strategies can be employed to mitigate this risk?' Facilitate a class discussion where students share their ideas on pivot selection and alternative algorithms.

• Understand
• Analyze
• Evaluate
• Relationship Skills
• Self-Management

Activity 03

• Jigsaw
• 50 min · Whole Class

Whole Class: Efficiency Comparison

Run Merge Sort and Quick Sort on classroom laptops with identical datasets of increasing sizes. Project timings and recursion depths. Class discusses trade-offs in space, stability, and average versus worst-case scenarios.

Explain how Merge Sort guarantees a stable sort, unlike some other algorithms.

Facilitation Tip

During Whole Class: Efficiency Comparison, project a timer visible to all groups to keep the discussion focused on performance rather than completion time.

What to look for

On a slip of paper, ask students to write down one key difference between Merge Sort and Quick Sort regarding stability and one scenario where Merge Sort's guaranteed O(n log n) performance is advantageous over Quick Sort's average-case performance.

• Understand
• Analyze
• Evaluate
• Relationship Skills
• Self-Management

Activity 04

• Jigsaw
• 25 min · Individual

Individual: Recursion Tree Tracing

Students draw recursion trees for small arrays in Merge Sort and Quick Sort. Label partition points and merge costs. Compare trees to predict performance on unbalanced data.

Compare the recursive nature of Merge Sort and Quick Sort.

What to look for

Present students with a small unsorted array (e.g., [5, 2, 8, 1, 9]). Ask them to trace the first step of Quick Sort, explaining their pivot choice and showing the resulting partitioned array. Then, ask them to trace the first merge step of Merge Sort on a similar small array, showing the two sorted sub-arrays and the result of their merge.

• Understand
• Analyze
• Evaluate
• Relationship Skills
• Self-Management

A few notes on teaching this unit

Teach these algorithms by starting with physical models before code. Research shows that students who manipulate physical arrays first transfer the logic more accurately to recursive functions. Avoid rushing to pseudocode; let students articulate the steps in their own words. Emphasize base cases explicitly, as recursion termination is the most common sticking point.

Students will confidently explain the steps of Merge Sort and Quick Sort, compare their efficiencies, and trace recursion trees independently. They will justify pivot choices, identify stability, and connect time complexity to real data sets.

---

Watch Out for These Misconceptions

• During Pair Coding: Quick Sort Implementation, listen for students to claim that Quick Sort is always faster than Merge Sort regardless of input.

  During Pair Coding: Quick Sort Implementation, have pairs deliberately choose a poor pivot (e.g., first or last element) on a nearly sorted array and measure the runtime to observe O(n^2) behavior firsthand.

• During Card Simulation: Merge Sort Steps, some may assume that the final merge step automatically preserves the original order of equal elements.

  During Card Simulation: Merge Sort Steps, instruct groups to use duplicate values and mark their original positions with small stickers, then verify that their merge maintains the initial order.

• During Recursion Tree Tracing, students may worry that recursion will run forever like iteration.

  During Recursion Tree Tracing, ask students to highlight the base case on their diagrams and explain why subarrays of size one halt the recursion, connecting the visual to code termination.

---

Methods used in this brief

• Jigsaw