Insertion Sort

Learning Objectives

By the end of this lesson, learners will be able to:

• Explain how Insertion Sort builds a sorted prefix.
• Trace the key–shift–insert process step by step.
• Analyze time complexity in best and worst cases.
• Implement Insertion Sort correctly without off-by-one errors.
• Evaluate when Insertion Sort is preferable to other sorting methods.

Aligned with Bloom’s Taxonomy: Understand → Apply → Analyze → Evaluate

Backward Design Approach

• Stage 1 – Desired Results: Conceptual clarity of sorted prefix + operational accuracy.
• Stage 2 – Evidence: Learner can trace algorithm steps and explain stability.
• Stage 3 – Learning Plan: Mental model → structured steps → demo → self-check → extension.

Core Concept

Insertion Sort maintains a growing sorted prefix. Each new element (the key) is compared leftward, larger elements are shifted, and the key is inserted into the correct position.

Algorithm Process

1. Assume the first element is sorted.
2. Select the next element as the key.
3. Shift larger elements rightward.
4. Insert the key into the correct gap.
5. Repeat until the list is fully sorted.

Performance & Properties

• Worst Case: O(n²)
• Best Case: O(n) when nearly sorted
• Space: O(1) (in-place)
• Stable: Yes

Common Learner Errors

• Failing to store the key before shifting.
• Incorrect loop boundaries.
• Breaking stability using incorrect comparison.

Formative Assessment

• Trace the algorithm on: [5, 3, 4, 1]
• Why does Insertion Sort run in O(n) on nearly sorted arrays?
• How does stability influence algorithm choice?

Transfer & Extension

Learners compare Insertion Sort with Selection Sort and Merge Sort, evaluating trade-offs in efficiency, memory use, and stability.

Instructional Design Framework