👋 Welcome Gophers! In this lesson, we are going to look at how the insertion sort algorithm works, explore its time complexity, and see when you might want to use it over other sorting algorithms.
How Insertion Sort Works
The insertion sort algorithm is a simple comparison-based sorting algorithm. It builds the final sorted array one element at a time by iterating through a list of items, comparing each item to the ones that came before it, and inserting it into the correct position in the already-sorted portion of the list.
Think of it like sorting playing cards in your hand. You pick up cards one at a time and insert each card into its correct position among the cards you’re already holding.
Here’s the basic process:
- Start with the second element (the first element is considered already sorted)
- Compare it with elements before it
- Shift larger elements one position to the right
- Insert the current element into its correct position
- Move to the next element and repeat
Time Complexity
- Best Case: O(n) - when the array is already sorted
- Average Case: O(n²) - typical random data
- Worst Case: O(n²) - when the array is sorted in reverse order
- Space Complexity: O(1) - sorts in place with only a constant amount of extra space
When to Use Insertion Sort
Despite its O(n²) worst-case complexity, insertion sort has some practical advantages:
- Small datasets: Very efficient for small arrays or lists
- Nearly sorted data: Performs well when the data is already partially sorted
- Stable sort: Maintains the relative order of equal elements
- Online algorithm: Can sort data as it’s received
- In-place sorting: Requires minimal extra memory
Visual Representation
Here’s how insertion sort works visually:
<svg viewBox="0 0 600 400" xmlns="http://www.w3.org/2000/svg" style="background-color: #1a1a1a; font-family: monospace;">
<!-- Step 1: Initial array -->
<text x="20" y="30" fill="#e0e0e0" font-size="14">Step 1: Initial array [5, 2, 4, 3, 1]</text>
<rect x="30" y="50" width="40" height="40" fill="#4a4a4a" stroke="#888" stroke-width="2"/>
<text x="50" y="80" fill="#fff" text-anchor="middle" font-size="16">5</text>
<rect x="80" y="50" width="40" height="40" fill="#ff6b6b" stroke="#ff6b6b" stroke-width="2"/>
<text x="100" y="80" fill="#fff" text-anchor="middle" font-size="16">2</text>
<rect x="130" y="50" width="40" height="40" fill="#4a4a4a" stroke="#888" stroke-width="2"/>
<text x="150" y="80" fill="#fff" text-anchor="middle" font-size="16">4</text>
<rect x="180" y="50" width="40" height="40" fill="#4a4a4a" stroke="#888" stroke-width="2"/>
<text x="200" y="80" fill="#fff" text-anchor="middle" font-size="16">3</text>
<rect x="230" y="50" width="40" height="40" fill="#4a4a4a" stroke="#888" stroke-width="2"/>
<text x="250" y="80" fill="#fff" text-anchor="middle" font-size="16">1</text>
<!-- Step 2: Insert 2 -->
<text x="20" y="150" fill="#e0e0e0" font-size="14">Step 2: Insert 2 into sorted portion</text>
<rect x="30" y="170" width="40" height="40" fill="#4a4a4a" stroke="#888" stroke-width="2"/>
<text x="50" y="200" fill="#fff" text-anchor="middle" font-size="16">2</text>
<rect x="80" y="170" width="40" height="40" fill="#4a4a4a" stroke="#888" stroke-width="2"/>
<text x="100" y="200" fill="#fff" text-anchor="middle" font-size="16">5</text>
<rect x="130" y="170" width="40" height="40" fill="#4a4a4a" stroke="#888" stroke-width="2"/>
<text x="150" y="200" fill="#fff" text-anchor="middle" font-size="16">4</text>
<rect x="180" y="170" width="40" height="40" fill="#4a4a4a" stroke="#888" stroke-width="2"/>
<text x="200" y="200" fill="#fff" text-anchor="middle" font-size="16">3</text>
<rect x="230" y="170" width="40" height="40" fill="#4a4a4a" stroke="#888" stroke-width="2"/>
<text x="250" y="200" fill="#fff" text-anchor="middle" font-size="16">1</text>
<!-- Step 3: Final sorted array -->
<text x="20" y="270" fill="#e0e0e0" font-size="14">Step 3: Final sorted array [1, 2, 3, 4, 5]</text>
<rect x="30" y="290" width="40" height="40" fill="#51cf66" stroke="#51cf66" stroke-width="2"/>
<text x="50" y="320" fill="#fff" text-anchor="middle" font-size="16">1</text>
<rect x="80" y="290" width="40" height="40" fill="#51cf66" stroke="#51cf66" stroke-width="2"/>
<text x="100" y="320" fill="#fff" text-anchor="middle" font-size="16">2</text>
<rect x="130" y="290" width="40" height="40" fill="#51cf66" stroke="#51cf66" stroke-width="2"/>
<text x="150" y="320" fill="#fff" text-anchor="middle" font-size="16">3</text>
<rect x="180" y="290" width="40" height="40" fill="#51cf66" stroke="#51cf66" stroke-width="2"/>
<text x="200" y="320" fill="#fff" text-anchor="middle" font-size="16">4</text>
<rect x="230" y="290" width="40" height="40" fill="#51cf66" stroke="#51cf66" stroke-width="2"/>
<text x="250" y="320" fill="#fff" text-anchor="middle" font-size="16">5</text>
</svg>
Quiz Time
Validate what you’ve learned in this lesson by attempting these quiz questions: