Insertion Sort Algorithm: Pseudocode and Explanation

In the previous article, we explored how insertion sort works through visual examples and step-by-step explanations. Now, let’s dive deeper into the algorithmic details by examining the pseudocode for a basic insertion sort algorithm. By the end of this article, you’ll have a clear understanding of how to implement insertion sort in any programming language.

Prerequisites:

Understanding the Key Concepts

Before we look at the pseudocode, let’s understand the key concepts used in insertion sort:

  1. Current Element (key):

    • The element we’re currently trying to insert into its correct position
    • Selected from the unsorted portion of the array
    • Also called the “key” element

  2. Sorted Portion:

    • The left part of the array that’s already sorted
    • Initially contains just the first element
    • Grows from left to right as the algorithm progresses

  3. Comparison Index (j):

    • Used to scan through the sorted portion
    • Helps find the correct position for the current element to be inserted
    • Moves from right to left in the sorted portion

Algorithm for Iterative Insertion Sort

  1. Start with First Element:

    • Consider the first element as a sorted portion of length 1
    • The rest of the array is the unsorted portion

  2. Select Next Element:

    • Take the first element from the unsorted portion
    • This becomes our current element (key)

  3. Find Correct Position:

    • Compare key with each element in the sorted portion
    • Move elements greater than key one position ahead
    • Continue until you find the correct position

  4. Insert Element:

    • Place the key in its correct position
    • The sorted portion now grows by one element

  5. Repeat:

    • Continue steps 2-4 until the entire array is sorted

Pseudocode for Iterative Insertion Sort

Here’s the pseudocode for the iterative approach:

def insertionSort(arr):
  n = len(arr)
  
  # Start from the second element (index 1)
  for i in range(1, n):
    # Store the current element as key
    key = arr[i]
    
    # Initialize the position for comparison to the element before current
    j = i - 1
    
    # Move elements of arr[0..i-1], that are greater than key, to one position ahead
    # of their current position
    while j >= 0 and arr[j] > key:
      arr[j + 1] = arr[j]  # Shift elements to the right
      j -= 1              # Move to the next element to the left
    
    # Insert the key (current element) into its correct position
    arr[j + 1] = key

Example Walkthrough

Let’s trace the iterative pseudocode with the array [5, 2, 8, 1, 9]. The vertical bar (|) separates the sorted portion (left) from the unsorted portion (right):

  1. First Iteration (i = 1):

    • Initial array: [5 | 2, 8, 1, 9] (5 is our sorted portion)
    • We pick key = 2 (first element from unsorted portion), i = 1, key = 2, j = 0
    • Compare 2 with 5: Since 5 > 2, we shift 5 one position right
    • arr[1] = 5, j = -1
    • Place 2 in the empty spot
    • arr[0] = 2
    • Result: [2, 5 | 8, 1, 9] (now first two elements are sorted)

  2. Second Iteration (i = 2):

    • Current array: [2, 5 | 8, 1, 9]
    • We pick key = 8, i = 2, key = 8, j = 1
    • Compare 8 with 5: Since 5 < 8, 8 is already in correct position
    • Result: [2, 5, 8 | 1, 9] (first three elements are sorted)

  3. Third Iteration (i = 3):

    • Current array: [2, 5, 8 | 1, 9]
    • We pick key = 1, i = 3, key = 1, j = 2
    • Compare and shift: 8 > 1, so 8 moves right (arr[3] = 8), j = 1
    • Then 5 > 1, so 5 moves right (arr[2] = 5), j = 0
    • Then 2 > 1, so 2 moves right (arr[1] = 2), j = -1
    • Place 1 in the empty spot at beginning
    • arr[0] = 1
    • Result: [1, 2, 5, 8 | 9] (first four elements are sorted)

  4. Fourth Iteration (i = 4):

    • Current array: [1, 2, 5, 8 | 9]
    • We pick key = 9, i = 4, key = 9, j = 3
    • Compare 9 with 8: Since 8 < 9, 9 is already in correct position
    • Result: [1, 2, 5, 8, 9 |] (entire array is now sorted!)

What’s Next?

Now that you understand the pseudocode, you might want to: