Sorting Algorithms: Insertion Sort Implementation

Active learning helps students grasp sorting algorithms because abstract concepts become concrete through hands-on practice. For insertion sort, tracing each step with physical objects or code makes the shifting process visible and memorable, which is essential for understanding why it builds the sorted portion from left to right.

• Class 12
• Computer Science
• 4 activities
• 25 min–40 min

Learning Objectives

1. Implement insertion sort algorithm in Python to sort a given list of integers.
2. Trace the execution of insertion sort on a small dataset, identifying comparisons and element shifts at each step.
3. Analyze the time complexity of insertion sort for best-case, average-case, and worst-case scenarios.
4. Compare the performance of insertion sort with bubble sort for nearly sorted and reverse-sorted arrays.
5. Justify the selection of insertion sort for specific scenarios, such as sorting small datasets or online sorting.

Experiential Learning

⏱ 30 min·Small Groups

Hands-on Simulation: Card Sort Relay

Distribute shuffled cards numbered 1-20 to small groups. One student sorts by insertion method while others time and count shifts. Groups compare results and discuss observations. Rotate roles for two rounds.

Prepare & details

Describe the step-by-step process of insertion sort.

Facilitation Tip: During the Card Sort Relay, ensure students physically move cards in the sorted portion to show how larger elements shift right to make space for the new element.

Setup: Flexible classroom arrangement with desks pushed aside for activity space, or standard rows with group-work stations rotated in sequence. Works in standard Indian classrooms of 40–48 students with basic furniture and no specialist equipment.

Materials: Chart paper and sketch pens for group recording, Everyday household or locally available objects relevant to the concept, Printed reflection prompt cards (one set per group), NCERT textbook for connecting activity outcomes to chapter content, Student notebook for individual reflection journalling

• Apply
• Analyze
• Evaluate
• Self-Awareness
• Self-Management
• Social Awareness

Experiential Learning

⏱ 40 min·Pairs

Pair Programming: Implement Insertion Sort

Pairs write Python code for insertion sort on given arrays. Test with random, sorted, and reverse-sorted inputs. Debug together and note swap counts. Share one insight with class.

Prepare & details

Compare insertion sort's efficiency with bubble sort for nearly sorted data.

Facilitation Tip: When students pair program, encourage them to test with at least two arrays: one nearly sorted and one reverse sorted, to observe the algorithm’s adaptive nature.

Setup: Flexible classroom arrangement with desks pushed aside for activity space, or standard rows with group-work stations rotated in sequence. Works in standard Indian classrooms of 40–48 students with basic furniture and no specialist equipment.

Materials: Chart paper and sketch pens for group recording, Everyday household or locally available objects relevant to the concept, Printed reflection prompt cards (one set per group), NCERT textbook for connecting activity outcomes to chapter content, Student notebook for individual reflection journalling

• Apply
• Analyze
• Evaluate
• Self-Awareness
• Self-Management
• Social Awareness

Experiential Learning

⏱ 25 min·Whole Class

Whiteboard Walkthrough: Trace Execution

Whole class traces insertion sort on a large array drawn on whiteboard. Teacher or student leads, marking sorted portion and shifts with arrows. Pause for predictions at each step.

Prepare & details

Justify why insertion sort might be preferred for small datasets.

Facilitation Tip: For the Whiteboard Walkthrough, have students draw arrows to mark the boundaries of the sorted and unsorted portions with each insertion step.

Setup: Flexible classroom arrangement with desks pushed aside for activity space, or standard rows with group-work stations rotated in sequence. Works in standard Indian classrooms of 40–48 students with basic furniture and no specialist equipment.

Materials: Chart paper and sketch pens for group recording, Everyday household or locally available objects relevant to the concept, Printed reflection prompt cards (one set per group), NCERT textbook for connecting activity outcomes to chapter content, Student notebook for individual reflection journalling

• Apply
• Analyze
• Evaluate
• Self-Awareness
• Self-Management
• Social Awareness

Experiential Learning

⏱ 35 min·Individual

Data Challenge: Efficiency Test

Individuals run insertion and bubble sort codes on datasets of size 10, 50, 100. Record execution times. Plot results and analyse trends in small group discussions.

Prepare & details

Describe the step-by-step process of insertion sort.

Facilitation Tip: In the Efficiency Test, provide a timer or counter so students can measure comparisons and shifts for different input sizes, reinforcing the empirical evidence.

Setup: Flexible classroom arrangement with desks pushed aside for activity space, or standard rows with group-work stations rotated in sequence. Works in standard Indian classrooms of 40–48 students with basic furniture and no specialist equipment.

Materials: Chart paper and sketch pens for group recording, Everyday household or locally available objects relevant to the concept, Printed reflection prompt cards (one set per group), NCERT textbook for connecting activity outcomes to chapter content, Student notebook for individual reflection journalling

• Apply
• Analyze
• Evaluate
• Self-Awareness
• Self-Management
• Social Awareness

Teaching This Topic

Experienced teachers approach insertion sort by first making the process visual and tactile, using card sorting to build intuition before moving to code. They avoid rushing to the Python implementation and instead focus on the mechanics of shifting elements. Research shows that students retain the concept better when they physically manipulate elements, so prioritize simulations over abstract explanations. Teachers should also highlight the algorithm’s adaptive nature by comparing its performance on different input types, which helps students move beyond the fixed O(n^2) myth.

What to Expect

Successful learning looks like students accurately simulating the algorithm with cards, writing correct Python code, and explaining the difference between comparisons and shifts. They should confidently trace the algorithm on small arrays and justify why insertion sort adapts to nearly sorted data.

Watch Out for These Misconceptions

Common Misconception

During Hands-on Simulation: Card Sort Relay, watch for students treating insertion sort like bubble sort by swapping adjacent elements only.

What to Teach Instead

In the Card Sort Relay, emphasize that students must shift all larger elements in the sorted portion to the right at once to make space for the new element. Ask them to verbalize why multiple cards move together, not just adjacent swaps.

Common Misconception

During Pair Programming: Implement Insertion Sort, watch for students assuming insertion sort always performs the same number of comparisons regardless of input order.

What to Teach Instead

After implementing the algorithm, have students test it on nearly sorted data, reverse sorted data, and random data. Ask them to count comparisons for each case and compare the results to highlight the adaptive nature of insertion sort.

Common Misconception

During Whiteboard Walkthrough: Trace Execution, watch for students starting the sorted portion from the end of the array.

What to Teach Instead

On the whiteboard, clearly label the leftmost element as the starting sorted portion. Use arrows to show how the sorted portion grows to the right with each insertion, and ask students to predict the next step actively.

Assessment Ideas

Quick Check

After Hands-on Simulation: Card Sort Relay, present students with a partially sorted list, e.g., [5, 1, 4, 2, 8]. Ask them to write down the state of the list after the third element (4) has been inserted into the sorted portion [1, 5].

Exit Ticket

After Pair Programming: Implement Insertion Sort, ask students to write on a slip of paper: 1. One advantage of insertion sort over bubble sort for nearly sorted data. 2. One scenario where insertion sort is a good choice.

Discussion Prompt

During Data Challenge: Efficiency Test, facilitate a class discussion: 'Imagine you are designing a system to sort user search results as they are typed. Would insertion sort be a suitable algorithm? Why or why not? Consider its time complexity and adaptive nature.'

Extensions & Scaffolding

• Challenge students to implement insertion sort with a custom comparator function that sorts strings by length instead of lexicographical order.
• For students struggling with the shifting logic, provide partially filled trace tables where they only need to write the comparisons and shifts for the next insertion step.
• Deeper exploration: Ask students to research why insertion sort is often used in hybrid algorithms like Timsort, and present their findings to the class.

Key Vocabulary

Insertion Sort	A simple sorting algorithm that builds the final sorted array one item at a time. It iterates through the input array and for each element, it finds the correct position within the already sorted portion and inserts it there.
In-place Sorting	A sorting algorithm that sorts elements within the same data structure without requiring significant additional memory. Insertion sort is an in-place algorithm.
Stable Sort	A sorting algorithm that preserves the relative order of equal elements in the input array. Insertion sort is a stable sorting algorithm.
Adaptive Sort	A sorting algorithm that performs better when the input array is already partially sorted. Insertion sort is an adaptive sorting algorithm.