Insertion Sort

Insertion Sort is an efficient algorithm for sorting a small number of elements. The most common illustration used for demonstrating insertion sort is playing cards. We start with an empty left hand and the cards face down on the table. We then remove one card at a time from the table and insert it into the correct position in the left hand. To find the correct position of the card, we compare it with each of the cards already in hand.

The Code

def insertion_sort(a):
    if len(a) <= 1:
        return a

    for j in range(1, len(a)):
        key = a[j]
        i = j - 1
        while i >= 0 and a[i] > key:
            a[i+1] = a[i]
            i = i-1
        a[i+1] = key

    return a

a = [5, 2, 4, 6, 1, 3]

sorted_arr = insertion_sort(a)
print(sorted_arr)

function insertionSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    let key = arr[i];
    let j = i - 1;
    while (j >= 0 && arr[j] > key) {
      arr[j + 1] = arr[j];
      j = j - 1;
    }
    arr[j + 1] = key;
  }
  return arr;
}

let arr = [9, 1, 8, 2, 7, 3, 6, 5, 4];
sortedArr = insertionSort(arr);
console.log(sortedArr);

def insertion_sort(a)
  return "Elements sorted" if a.count <= 1

  arr_range = a.count - 1
  for i in 1..arr_range do
    key = a[i]
    j = i - 1
    while j >= 0 && a[j] > key
      a[j + 1] = a[j]
      j = j - 1
    end
    a[j+ 1] = key
  end

  return a
end

a = [5, 2, 4, 6, 1, 3]
sorted = insertion_sort(a)
puts sorted

package main

import "fmt"

func insertion_sort(a []int) {
	if len(a) <= 1 {
		return
	}

	for i := 1; i < len(a); i++ {
		key := a[i]
		j := i - 1
		for j >= 0 && a[j] > key {
			a[j+1] = a[j]
			j--
		}

		a[j+1] = key
	}
}

func main() {
	var a = []int{5, 2, 4, 6, 1, 3}
	insertion_sort(a)
	fmt.Println(a)
}

In the code snippets above, we see an implementation of Insertion Sort. Within our for loop, the temp variable, key, tracks the current element. We also keep track of the 'j - 1' element using a variable 'i'. If the element in i is greater than the key, then we have to swap those elements by setting a[i + 1] (or j in the first iteration) to the value of a[i]. This pattern continues until there are no more values before 'j' that are greater than itself. Finally, using our temp variable (key), we set that equal to the current position of 'j'. That is insertion sort! (Note: The purpose of a insertion sort is to sort an array in-place. But I stored the sorted array in a variable called 'sorted' in some of the code snippets to help output the array to the user. Just a personal preference to avoid creating a util function.)

The Analysis

All things considered, Insertion Sort is pretty inefficient. It works best when working with smaller datasets. This is due to the double loop required for the algorithm to work. However, it is still an effective in-place sorting algorithm.

Time Complexities:

• Best Case: O(n) - If the list is already sorted, than additional sorts are required.
• Average Case: O(n²) - If some of the list is unsorted, then the algorithm still requires an additional loop of the list to sort items.
• Worst Case: O(n²) - If the list is reverse sorted. The time complexity does not change from average, but you can expect the time to sort to increase.

Space Complexity

• Auxillary Space: O(1) - One of the advantages for Insertion Sort is its space complexity! Because it doesn't require extra allocation of space to work, the space complexity is O(1) additional space, making it an space-efficient algorithm.

The Takeaway

Insertion Sort is the first sorting algorithm I learned about in my data structures and algorithms course. Because of that, it holds a special place in my heart. Conceptually, it is quite simple to understand, but actually writing the code for it is a different story. Yes, it only requires a few lines of code, but imagine having to write this out during an interview by memory? Unless you have researched and put a good amount of thought into this algorithm, writing this from scratch can be tricky!