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.

• Year 11
• Computing
• 4 activities
• 25 min–50 min

Learning Objectives

1. Compare the time complexity and space complexity of Merge Sort and Quick Sort algorithms.
2. Analyze the recursive steps involved in both Merge Sort and Quick Sort to explain their divide-and-conquer strategies.
3. Evaluate the impact of pivot selection on the performance of Quick Sort, identifying scenarios leading to worst-case complexity.
4. Explain the conditions under which Merge Sort guarantees a stable sort, contrasting it with potentially unstable sorts.
5. Design a pseudocode representation for either Merge Sort or Quick Sort, demonstrating a clear understanding of its logic.

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.

Prepare & details

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.

Setup: Flexible seating for regrouping

Materials: Expert group reading packets, Note-taking template, Summary graphic organizer

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

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.

Prepare & details

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.

Setup: Flexible seating for regrouping

Materials: Expert group reading packets, Note-taking template, Summary graphic organizer

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

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.

Prepare & details

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.

Setup: Flexible seating for regrouping

Materials: Expert group reading packets, Note-taking template, Summary graphic organizer

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

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.

Prepare & details

Compare the recursive nature of Merge Sort and Quick Sort.

Setup: Flexible seating for regrouping

Materials: Expert group reading packets, Note-taking template, Summary graphic organizer

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

Teaching This Topic

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.

What to Expect

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

Common Misconception

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

What to Teach Instead

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.

Common Misconception

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

What to Teach Instead

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.

Common Misconception

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

What to Teach Instead

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.

Assessment Ideas

Quick Check

After Card Simulation: Merge Sort Steps, show a small unsorted array on the board and ask students to trace the first merge step in writing, identifying the two sorted halves and the merged result.

Discussion Prompt

During Whole Class: Efficiency Comparison, ask students to share their timing results from Quick Sort implementations with different pivot strategies and discuss which strategies mitigate worst-case scenarios.

Exit Ticket

After Individual: Recursion Tree Tracing, collect each student’s labeled tree to check that they marked the base case correctly and traced the partitioning steps without skipping subarrays.

Extensions & Scaffolding

• Challenge: Ask students to implement Quick Sort with median-of-three pivot selection and compare its performance to the random pivot version using a 1000-element unsorted array.
• Scaffolding: Provide pre-labeled recursion tree diagrams with gaps for students to fill in values and pointers during Recursion Tree Tracing.
• Deeper exploration: Explore hybrid sorts by having students modify Merge Sort to switch to insertion sort for small subarrays (e.g., size ≤ 10) and measure the performance change.

Key Vocabulary

Divide and Conquer	An algorithmic paradigm that recursively breaks down a problem into two or more sub-problems of the same or related type, until these become simple enough to be solved directly, then combines their solutions.
Pivot	An element in an array that is chosen by the Quick Sort algorithm to partition the other elements into two sub-arrays according to whether they are less than or greater than the pivot.
Partitioning	The process in Quick Sort where elements are rearranged around a chosen pivot, ensuring all elements smaller than the pivot come before it, and all elements larger come after it.
Stable Sort	A sorting algorithm that preserves the relative order of equal elements in the input array. If two elements have the same value, their original order is maintained in the sorted output.
Time Complexity	A measure of how the execution time of an algorithm grows as the input size increases, often expressed using Big O notation.
Space Complexity	A measure of the amount of memory an algorithm requires to run as a function of the input size, also often expressed using Big O notation.