Starter Activity (5 mins)
Card Sorting Challenge!
Example Answers & Discussion Points:
- 1. You'd take the first card (it's sorted by itself). Then take the second card; compare it with the first and insert it before or after. Take the third card; compare it with the cards in your sorted hand (from right to left, or left to right finding the spot) and shift cards if necessary to make space, then insert it. Repeat for all cards.
- 2. Probably not very efficient for 1000 cards. For each new card, you might have to compare it with many already sorted cards and potentially shift many cards to make space. This could involve a lot of comparisons and movements.
- This manual method is very similar to how Insertion Sort works!
Lesson Outcomes
By the end of this lesson, you should be able to:
- Describe the Insertion SortA simple sorting algorithm that builds the final sorted list one item at a time. It iterates through an input list and for each element, inserts it into its correct position in an already sorted part of the list. algorithm.
- Explain how Insertion Sort works by maintaining a sorted sub-listIn insertion sort, this is the portion of the list (usually at the beginning) that is already in correct order. Each new element from the unsorted part is inserted into this sub-list..
- Trace the execution of an Insertion Sort algorithm on a given list of data, showing comparisons and element shifts.
- Identify the advantages and disadvantages of Insertion Sort.
- Understand its efficiency characteristics (e.g., good for small or nearly sorted lists).
Introduction to Insertion Sort
Insertion SortA simple sorting algorithm that builds the final sorted list one item at a time. It iterates through an input list and for each element, inserts it into its correct position in an already sorted part of the list. is another simple sorting algorithm that builds the final sorted list one item at a time. It's much like how many people sort a hand of playing cards.
The algorithm iterates through the input elements. For each element, it finds the correct position in the already sorted part of the list and inserts it there. This involves shifting other elements to the right to make space.
How it Works (Operation):
- Start with the second element in the list (assume the first element by itself is a sorted sub-listIn insertion sort, this is the portion of the list (usually at the beginning) that is already in correct order. Each new element from the unsorted part is inserted into this sub-list. of size 1).
- Take the current element (let's call it the 'key') and compare it with the elements in the sorted sub-list to its left.
- If the key is smaller than an element in the sorted sub-list, shift that sorted element one position to the right to make space for the key.
- Continue shifting elements to the right until you find the correct position for the key (i.e., an element smaller than or equal to the key is found, or the beginning of the sorted sub-list is reached).
- Insert the key into that correct position.
- Repeat steps 2-5 for all remaining unsorted elements, expanding the sorted sub-list one element at a time.
Insertion Sort is efficient for small datasets or lists that are already partially sorted. Hover over keywordsThis is an example tooltip! for definitions.
Insertion Sort in Action
Interactive Simulation
Enter a list of numbers (comma-separated, e.g., 5,2,8,1,9) or use the default. Then, step through the Insertion Sort process.
Task 1: Tracing Insertion Sort (Max 4 points)
Consider the list: [5, 2, 4, 1]. Show the state of the list after each element from the unsorted portion is picked and inserted into its correct place in the sorted portion.
Example Trace for [5, 2, 4, 1]:
- Initial: [5, 2, 4, 1] (Sorted: [5], Unsorted: [2, 4, 1])
- Pick 2 (key). Compare with 5. 2 < 5. Shift 5 right. Insert 2. List: [2, 5, 4, 1] (Sorted: [2, 5], Unsorted: [4, 1])
- Pick 4 (key). Compare with 5. 4 < 5. Shift 5 right. Compare with 2. 4 > 2. Insert 4. List: [2, 4, 5, 1] (Sorted: [2, 4, 5], Unsorted: [1])
- Pick 1 (key). Compare with 5. 1 < 5. Shift 5 right. Compare with 4. 1 < 4. Shift 4 right. Compare with 2. 1 < 2. Shift 2 right. Insert 1. List: [1, 2, 4, 5] (Sorted: [1, 2, 4, 5], Unsorted: [])
- List is sorted.
(For 4 marks, clearly show which element is picked (key), the comparisons made within the sorted sub-list, any shifts, and the state of the list after each insertion.)
Advantages & Disadvantages of Insertion Sort
When is it a Good Fit?
Advantages:
- Simple to understand and implement.
- Efficient for small datasets.
- Very efficient for lists that are already nearly sortedIf a list has only a few elements out of place, insertion sort can sort it very quickly, approaching O(n) time complexity. (adaptive). If the list is sorted, it has a best-case time complexity of O(n).
- It's an in-place sortA sorting algorithm that sorts the elements within the original array or list, using only a constant amount of extra storage space (or a very small, logarithmic amount)., requiring only a constant amount O(1) of additional memory space.
- It's a stable sortA sorting algorithm where two objects with equal keys appear in the same order in the sorted output as they appear in the input array to be sorted. Insertion sort is stable. (maintains the relative order of equal elements).
- Good for online algorithmsAlgorithms that process input piece-by-piece in a serial fashion, without having the entire input available from the start. Insertion sort can easily sort data as it arrives. (can sort a list as it receives it).
Disadvantages:
- Inefficient for large, random lists. Its average and worst-case time complexity (Insertion Sort)Worst-case and average-case O(n²), best-case O(n) if the list is already sorted. is O(n²).
- Involves many element shifts if an element needs to be inserted near the beginning of the sorted sub-list.
Real-World Context for Insertion Sort
Due to its O(n²) complexity for larger lists, Insertion Sort isn't the primary choice for sorting huge datasets. However, its strengths make it suitable for specific scenarios:
- Small Datasets: For lists with a small number of items (e.g., less than 10-20), Insertion Sort can actually be faster than more complex algorithms like Merge Sort or Quick Sort because it has less overhead.
- Nearly Sorted Data: If a list is already mostly sorted, Insertion Sort performs very well, approaching O(n) time complexity. This makes it useful for re-sorting a list after a few new items have been added.
- Online Sorting: When data arrives one item at a time and needs to be incorporated into a sorted list immediately, Insertion Sort is a natural fit.
- Component in Hybrid Algorithms: More advanced sorting algorithms like Timsort (used in Python and Java) use Insertion Sort to efficiently sort small sub-arrays (partitions) created during their process.
- Educational Purposes: Like Bubble Sort, its simplicity makes it a good algorithm for teaching the fundamentals of sorting.
Insertion Sort Myth Busters!
Myth 1: "Insertion Sort is just as slow as Bubble Sort for all cases."
Reality: While both have an average and worst-case time complexityA measure of how the runtime of an algorithm scales with the input size. of O(n²), Insertion Sort is generally faster in practice than Bubble Sort for most random arrays. More importantly, Insertion Sort's best-case complexity is O(n) (for an already sorted list), whereas Bubble Sort's best case (with optimization) is also O(n), but Insertion Sort often performs fewer swaps overall and is more efficient on nearly sortedIf a list has only a few elements out of place, insertion sort can sort it very quickly, approaching O(n) time complexity. data.
Myth 2: "Insertion Sort always shifts every element in the sorted part for each new insertion."
Reality: Insertion Sort only shifts elements in the sorted sub-listIn insertion sort, this is the portion of the list (usually at the beginning) that is already in correct order. Each new element from the unsorted part is inserted into this sub-list. that are greater than the 'key' (the element being inserted). If the key is larger than all elements in the sorted sub-list, or if it's being inserted into an empty sorted sub-list (like the very first element), no shifts are needed for that particular insertion. The number of shifts depends on where the key belongs.
Task 2: Exam Practice Questions
Apply your knowledge to these exam-style questions.
1. Describe the main steps of an Insertion Sort algorithm when sorting a list into ascending order. [4 marks]
Mark Scheme:
- The list is conceptually divided into a sorted and an unsorted part / Starts with the first element as sorted. (1 mark)
- Take the next/first element from the unsorted part (this is the 'key'). (1 mark)
- Compare the key with elements in the sorted part, moving from right to left / find the correct position for the key in the sorted part. (1 mark)
- Shift elements in the sorted part that are greater than the key one position to the right to make space, and insert the key. (1 mark)
- Repeat until all elements from the unsorted part have been inserted into the sorted part. (1 mark for repetition/completion)
(Award up to 4 marks for a clear, step-by-step description covering these points.)
2. State one situation where Insertion Sort would be a more efficient choice than Merge Sort, and explain why. [2 marks]
Mark Scheme:
- Situation: For small lists / arrays OR when the list is already nearly sorted. (1 mark)
- Reason: Insertion sort has less overhead than Merge Sort for small lists / For nearly sorted lists, Insertion Sort performs fewer comparisons and shifts, making its time complexity closer to O(n) which is better than Merge Sort's O(n log n) in this specific best-case scenario. (1 mark for a valid reason linked to the situation).
Key Takeaways
- Insertion SortA simple sorting algorithm that builds the final sorted list one item at a time. It iterates through an input list and for each element, inserts it into its correct position in an already sorted part of the list. builds a sorted list by taking elements one by one from the unsorted part and inserting them into their correct position in the already sorted sub-listIn insertion sort, this is the portion of the list (usually at the beginning) that is already in correct order. Each new element from the unsorted part is inserted into this sub-list..
- It iterates through the list, comparing the current element (key) with elements in the sorted portion and shifting larger elements to make space.
- Advantages: Simple, efficient for small lists, very efficient for nearly sorted lists (adaptive), in-place (O(1) extra space), stable.
- Disadvantages: Inefficient for large random lists (O(n²) time complexity (Insertion Sort)Worst-case and average-case O(n²), best-case O(n) if the list is already sorted.).
What's Next?
You've now explored the Insertion Sort algorithm!
You have now covered the three main sorting algorithms for GCSE (Bubble, Merge, Insertion). Consider these next steps:
- Reviewing and comparing the efficiencies and use cases of all three sorting algorithms.
- Moving on to other algorithm topics or programming fundamentals.
Extension Activities
1. Implement Insertion Sort in Pseudocode/Python
Try writing the pseudocode for Insertion Sort. If you're comfortable with Python, attempt to implement it as a Python function.
Challenge: Can you include the optimization where you stop shifting once the correct position is found (i.e., when the key is no longer smaller than the element to its left)?
2. Shell Sort (A Variation)
Shell Sort is an improvement over Insertion Sort for larger lists. It sorts elements that are far apart from each other first, then progressively reduces the gap between elements being compared and inserted.
Research Task: How does Shell Sort work? What is the concept of the "gap" sequence, and how does it help improve performance over a basic Insertion Sort?