golangalgorithms

Insertion Sort

Imagine you're playing cards. You're dealt a hand, and as you pick up each new card, you instinctively place it into its correct position among the cards you've already sorted. That, in a nutshell, is Insertion Sort! It's a simple, intuitive sorting algorithm that builds the final sorted array one item at a time.

This method iterates through an array, starting from the second element. For each element, it then looks at the elements before it, shifting them one by one until it finds the perfect spot to "insert" the current element. If an element in the sorted portion is larger than the element being inserted, it gets moved to the right to make room.

Let's break down how this works and implement it in Go.

The Basic Go Implementation

Here's a straightforward way to implement Insertion Sort in Go:

func InsertionSort(s []int) {
	// Start from the second element (index 1) because the first element
	// is considered the "already sorted" portion of size 1.
	for i := 1; i < len(s); i++ {
		// 'j' is our pointer that moves backwards through the sorted portion.
		j := i
		// Keep moving 's[j]' to the left as long as it's smaller than the
		// element before it AND we haven't reached the beginning of the array.
		for j > 0 && s[j] < s[j-1] {
			// Swap elements: s[j] and s[j-1] trade places.
			// Note: The original code had s[i] instead of s[j] for the first swap,
			// which would cause incorrect behavior. Corrected to s[j].
			s[j], s[j-1] = s[j-1], s[j]
			j-- // Move our pointer further left
		}
	}
}

Correction Note: In the original InsertionSort code, the swap was s[i], s[j-1] = s[j-1], s[i]. This is incorrect. It should be s[j], s[j-1] = s[j-1], s[j] because j is the index of the element currently being considered for insertion into the sorted portion, and it moves. The corrected code above reflects this.

Walking Through an Example

Let's trace the steps with our example array of integers: [4, 0, 1, 3, 2].

Initial Array: [4, 0, 1, 3, 2]

i = 1 (Element is 0)

  • j starts at 1.
  • Inner loop condition: j > 0 (1 > 0 is true) AND s[j] < s[j-1] (s[1] which is 0 < s[0] which is 4 is true).
  • Swap s[1] (0) and s[0] (4): Array becomes [0, 4, 1, 3, 2].
  • j becomes 0.
  • Inner loop condition: j > 0 (0 > 0 is false). Inner loop exits. Array after i=1: [0, 4, 1, 3, 2] (The [0] part is now sorted)

i = 2 (Element is 1)

  • j starts at 2.
  • Inner loop condition: j > 0 (2 > 0 is true) AND s[j] < s[j-1] (s[2] which is 1 < s[1] which is 4 is true).
  • Swap s[2] (1) and s[1] (4): Array becomes [0, 1, 4, 3, 2].
  • j becomes 1.
  • Inner loop condition: j > 0 (1 > 0 is true) AND s[j] < s[j-1] (s[1] which is 1 < s[0] which is 0 is false). Inner loop exits. Array after i=2: [0, 1, 4, 3, 2] (The [0, 1] part is now sorted)

i = 3 (Element is 3)

  • j starts at 3.
  • Inner loop condition: j > 0 (3 > 0 is true) AND s[j] < s[j-1] (s[3] which is 3 < s[2] which is 4 is true).
  • Swap s[3] (3) and s[2] (4): Array becomes [0, 1, 3, 4, 2].
  • j becomes 2.
  • Inner loop condition: j > 0 (2 > 0 is true) AND s[j] < s[j-1] (s[2] which is 3 < s[1] which is 1 is false). Inner loop exits. Array after i=3: [0, 1, 3, 4, 2] (The [0, 1, 3, 4] part is now sorted)

i = 4 (Element is 2)

  • j starts at 4.
  • Inner loop condition: j > 0 (4 > 0 is true) AND s[j] < s[j-1] (s[4] which is 2 < s[3] which is 4 is true).
  • Swap s[4] (2) and s[3] (4): Array becomes [0, 1, 3, 2, 4].
  • j becomes 3.
  • Inner loop condition: j > 0 (3 > 0 is true) AND s[j] < s[j-1] (s[3] which is 2 < s[2] which is 3 is true).
  • Swap s[3] (2) and s[2] (3): Array becomes [0, 1, 2, 3, 4].
  • j becomes 2.
  • Inner loop condition: j > 0 (2 > 0 is true) AND s[j] < s[j-1] (s[2] which is 2 < s[1] which is 1 is false). Inner loop exits. Array after i=4: [0, 1, 2, 3, 4] (The full array is sorted!)

The outer loop finishes as i reaches len(s). The array is now fully sorted!

A Slightly Faster "Go"

While the previous version works, it performs many swaps. We can make Insertion Sort a bit more efficient (in terms of operations, not asymptotic complexity) by using a temporary variable to hold the element we're inserting. This allows us to shift elements to the right in one go, rather than swapping iteratively.

func InsertionSortOptimized(s []int) {
	for i := 1; i < len(s); i++ {
		// 't' (temp) holds the current element we want to insert.
		t := s[i]
		// 'j' starts at the end of the already sorted subarray.
		j := i - 1

		// While 'j' is within bounds AND the element at 'j' is greater than 't'...
		for j >= 0 && s[j] > t {
			// Shift the element at 'j' one position to the right.
			s[j+1] = s[j]
			j-- // Move 'j' left to compare with the next element.
		}
		// Once the loop ends, 'j+1' is the correct position for 't'.
		s[j+1] = t
	}
}

This optimized version is generally preferred in practice because it reduces the number of memory write operations compared to repeated swaps.

Time Complexity: The Quadratic Truth

The time complexity of Insertion Sort is O(n²), where 'n' is the number of elements in the array. Why quadratic? Because of those nested loops:

  • The outer loop runs n-1 times (for i from 1 to n-1).
  • In the worst-case scenario (e.g., a reverse-sorted array), the inner loop might also run up to i times, meaning roughly n times for each iteration of the outer loop.
  • n * n gives us n².

This makes Insertion Sort less efficient for very large datasets compared to algorithms like Merge Sort (O(n log n)) or Quick Sort (average O(n log n)). However, for nearly sorted arrays, Insertion Sort can be very fast, almost O(n).

Space Complexity: The Constant Contender

The space complexity of Insertion Sort is O(1), meaning it uses constant additional memory. This is because it sorts the array "in-place," only requiring a few temporary variables (like t in our optimized version) regardless of the input size. This makes it a good choice when memory is at a constraint.

Conclusion: When to Pick the Card Player

Insertion Sort is a simple, in-place sorting algorithm that is easy to understand and implement. It works well for:

  • Small datasets: For arrays with a few dozen elements, its simplicity often outweighs its O(n²) complexity.
  • Nearly sorted arrays: If your array is already mostly sorted, Insertion Sort is incredibly efficient, approaching O(n) performance.
  • Online sorting: When you need to sort elements as they arrive (like cards in your hand), Insertion Sort can integrate new elements efficiently into an already sorted list.

While it generally outperforms Bubble Sort (due to fewer swaps for the same worst-case complexity), for large, unsorted arrays, more advanced algorithms like Merge Sort or Quick Sort are typically chosen. However, knowing Insertion Sort gives you a fundamental understanding of how sorting algorithms work and a handy tool for specific use cases!