How Insertion Sort Works?

by

Think about playing cards: you start with one card in your hand, then pick up cards one by one and slide each into its correct position. That’s exactly how insertion sort works. Let’s see it in action with this list:

[7, 3, 5, 2, 6]

Pass 1: Pick the 2nd card (Key = 3)

  • Your hand starts with 7.
  • You pick 3. Compare it with 7.
  • Since 3 is smaller, slide 7 to the right and put 3 in front.

Result:
[3, 7, 5, 2, 6]

Pass 2: Pick the 3rd card (Key = 5)

  • Now you hold [3, 7].
  • Pick 5. Compare it with 7 → 5 < 7, so slide 7 right.
  • Compare 5 with 3 → 5 > 3, stop here. Insert 5 between 3 and 7.

Result:
[3, 5, 7, 2, 6]

Pass 3: Pick the 4th card (Key = 2)

  • Your hand is [3, 5, 7].
  • Pick 2. Compare it with 7 → shift 7 right.
  • Compare with 5 → shift 5 right.
  • Compare with 3 → shift 3 right.
  • No cards left to compare. Place 2 at the start.

Result:
[2, 3, 5, 7, 6]

Pass 4: Pick the 5th card (Key = 6)

  • Your hand is [2, 3, 5, 7].
  • Pick 6. Compare it with 7 → shift 7 right.
  • Compare with 5 → 6 > 5, stop here. Insert 6 between 5 and 7.

Result:
[2, 3, 5, 6, 7]

Final Sorted List

After all passes, your cards (or numbers) are perfectly sorted:
[2, 3, 5, 6, 7]

package main

import (
	"fmt"
)

func insertionSort(numbers []int) {
	fmt.Println("Initial List:", numbers)

	// Loop through the list starting from the second element
	for currentIndex := 1; currentIndex &lt; len(numbers); currentIndex++ {
		currentValue := numbers[currentIndex] // The value we want to insert (like picking a card)
		position := currentIndex - 1          // Position to compare backward

		fmt.Printf("\nPass %d (Current Value = %d):\n", currentIndex, currentValue)

		// Shift larger values to the right
		for position >= 0 &amp;&amp; numbers[position] > currentValue {
			numbers[position+1] = numbers[position]
			position--
			fmt.Println("  Shifting:", numbers)
		}

		// Insert the current value at its correct position
		numbers[position+1] = currentValue
		fmt.Println("  Inserted:", numbers)
	}
}

func main() {
	numbers := []int{7, 3, 5, 2, 6}
	insertionSort(numbers)
	fmt.Println("\nFinal Sorted List:", numbers)
}


Output:

Initial List: [7 3 5 2 6]

Pass 1 (Current Value = 3):
  Shifting: [7 7 5 2 6]
  Inserted: [3 7 5 2 6]

Pass 2 (Current Value = 5):
  Shifting: [3 7 7 2 6]
  Inserted: [3 5 7 2 6]

Pass 3 (Current Value = 2):
  Shifting: [3 5 7 7 6]
  Shifting: [3 5 5 7 6]
  Shifting: [3 3 5 7 6]
  Inserted: [2 3 5 7 6]

Pass 4 (Current Value = 6):
  Shifting: [2 3 5 7 7]
  Inserted: [2 3 5 6 7]

Final Sorted List: [2 3 5 6 7]

Leave a Comment