Insertion Sort

Imagine organizing a messy bookshelf, placing each book where it belongs one by one. That’s the essence of Insertion Sort, inserting each data element into its correct position like finding the perfect spot for your favourite novel.

Process

Imagine you have a messy pile of playing cards and want to sort them in your hand, one by one. That’s the essence of Insertion Sort! Here’s how it works:

1. Start with one card: Consider the first element in your data as the sorted “hand.” It’s already in its rightful place.

2. Draw a new card: Look at the next element in the unsorted data (like drawing a new card).

3. Find the right spot: Compare the new card to each card in your sorted hand, starting from the “back” (highest/lowest depending on sorting order).

4. Make space: If you find a card bigger (or smaller) than the new one, shift all cards after it one position to the right (or left) to create a gap.

5. Insert the new card: Slide the new card into the empty space you just created, ensuring it’s now in its correct order within the sorted hand.

6. Repeat: Keep drawing new cards, comparing, shifting,

Pseudo Code

Code
function insertionSort(array):
  for i in range(1, len(array)):
    key = array[i]
    j = i - 1
    while j >= 0 and array[j] > key:
      array[j + 1] = array[j]  # Shift elements to create space
      j -= 1
    array[j + 1] = key  # Insert key in its correct position
  return array
Explanation
  1. The insertionSort function takes an array as input.
  2. A for loop iterates through the array, starting from the second element (index 1), assuming the first element is already sorted.
  3. Inside the loop, the current element (key) is stored for comparison and potential insertion.
  4. Another while loop iterates backwards from the element before the key (j = i - 1), comparing elements with the key.
  5. If an element encountered in the inner loop is greater than the key, it’s shifted one position to the right to create space for the key.
  6. The inner loop continues shifting elements until a smaller element is found or the beginning of the array is reached.
  7. After the inner loop, the key is inserted into its correct position, ensuring sorted order up to that point.
  8. After all iterations, the array is sorted.

Implementations

Kotlin

Golang