Insertion Sort
Learn how the Insertion Sort algorithm organizes data by building a sorted sublist.
Warm Up: Card Sorting
Sort the Cards
Click the highlighted card to start sorting it.
How Insertion Sort Works
The insertion sort algorithm works by building up a sorted sublist in the first part of the original list, while the remaining part of the list remains unsorted.
At the start, the sorted sublist contains just a single item (the first item). The algorithm goes through the unsorted sublist, item by item. As each item is examined (the key), it is moved into the correct position in the sorted sublist.
Key Concepts
- Pass: Each time the algorithm places an unsorted item into the correct position.
- Comparison: Checking an item from the unsorted list against the sorted list to find its place.
- Shift: Moving sorted items to the right to make space for the new item.
Efficiency
Insertion Sort is generally faster than Bubble Sort because it usually performs fewer comparisons per pass.
- Best Case: List is already sorted (O(N)).
- Worst Case: List is in reverse order (O(N²)).
Watch It In Action
Example Trace
Follow the algorithm step-by-step using the trace table below. This matches the standard pseudocode implementation.
Fill the Gaps
Order the Steps
Arrange the steps of the Insertion Sort algorithm.
Available Steps:
Your sequence:
Click items above to build your sequence
Keywords Memory Game
A-Level Only: Efficiency of Insertion Sort
Let's analyse the Time and Space complexity of Insertion Sort using Big O notation. The graph below compares the operations needed for Best Case (Linear O(n)) and Worst/Average Case (Polynomial O(n²)), alongside the Space Complexity (Constant O(1)). This matches the efficiency of Bubble Sort.