Algorithm Structure

Insertion sort uses nested loops: outer loop picks elements, inner loop finds the insertion position.

The Two Loops

Outer Loop: Iterates through unsorted elements (i from 1 to n-1)

• Picks the current element to insert

Inner Loop: Shifts elements and finds insertion position (j from i-1 down to 0)

• Compares current element with sorted elements
• Shifts larger elements right
• Stops when correct position is found

Algorithm Flow

Pseudocode

function insertionSort(arr):
    for i = 1 to n-1:
        current = arr[i]  // Element to insert
        j = i - 1
        
        // Shift elements greater than current
        while j >= 0 and arr[j] > current:
            arr[j + 1] = arr[j]  // Shift right
            j = j - 1
        
        arr[j + 1] = current  // Insert

Step-by-Step Trace

For array [5, 2, 8, 1, 9]:

i=1, current=2, j=0:

• arr[0]=5 > 2, shift: [5, 5, 8, 1, 9]
• j=-1, insert at 0: [2, 5, 8, 1, 9]

i=2, current=8, j=1:

• arr[1]=5 < 8, no shift
• Insert at 2: [2, 5, 8, 1, 9]

i=3, current=1, j=2:

• arr[2]=8 > 1, shift: [2, 5, 8, 8, 9]
• arr[1]=5 > 1, shift: [2, 5, 5, 8, 9]
• arr[0]=2 > 1, shift: [2, 2, 5, 8, 9]
• j=-1, insert at 0: [1, 2, 5, 8, 9]

i=4, current=9, j=3:

• arr[3]=8 < 9, no shift
• Insert at 4: [1, 2, 5, 8, 9] ✓

Implementation Preview

Key Points

1. In-place: Modifies array directly, O(1) extra space
2. Stable: Equal elements maintain relative order
3. Adaptive: Efficient for nearly sorted arrays
4. Simple: Easy to understand and implement

What’s Next?

Let’s see insertion sort in action with a full visualization.