W2202 Insertion Sort

Within these castle walls be forged Mavens of Computer Science ...

— Merlin, The Coder

Algorithm

Unlike Bubble Sort which only compares two elements at a time, insertion sort works by looking at each element and finding where it belongs in the sorted array. At its base, insertion sort is more complicated than bubble sort, but not by much:

• Iterate over the array
• For each element at index i, loop back through the array starting at i to 0
  • Similar to bubble sort, if the element on the left is larger than the element on the right, swap them
    • Because this starts by comparing i and i - 1, if the current element is not in place it will get swapped to i - 1. If it is still not in place in the next iteration, it will be swapped to i - 2, and so on until it is in the correct place
• After each iteration, all of the elements up to i + 1 will be in the correct order although not necessarily sorted in the context of the full array
• Unlike bubble sort, you only need to iterate through the array once. Once you reach the end, the array is sorted

Swap

You can use the same swap function as in bubble sort because you only need to be able to swap two adjacent elements at a time.

Performance Considerations

Similar to bubble sort, if you use a swap function then consider passing the array by reference instead of by value to avoid copying the entire array for each swap.

Additionally, in insertion sort, you can stop/break the inner loop once you reach two sorted elements. In other words, you only need to swap until the element on the left is smaller than the element on the right, at which point you can exit the loop.

Example

Here is an example with an array of 5 elements:

Array: [95, 47, 62, 33, 89] | Initial
  * Elements at indexes 0 (95) and 1 (47) are not in order (95 > 47), swapping.
Array: [47, 95, 62, 33, 89] | Swaps: 1
  * Elements at indexes 1 (95) and 2 (62) are not in order (95 > 62), swapping.
  * Elements at indexes 0 (47) and 1 (62) are already in order (47 < 62), nothing to swap
Array: [47, 62, 95, 33, 89] | Swaps: 1
  * Elements at indexes 2 (95) and 3 (33) are not in order (95 > 33), swapping.
  * Elements at indexes 1 (62) and 2 (33) are not in order (62 > 33), swapping.
  * Elements at indexes 0 (47) and 1 (33) are not in order (47 > 33), swapping.
Array: [33, 47, 62, 95, 89] | Swaps: 3
  * Elements at indexes 3 (95) and 4 (89) are not in order (95 > 89), swapping.
  * Elements at indexes 2 (62) and 3 (89) are already in order (62 < 89), nothing to swap
Array: [33, 47, 62, 89, 95] | Swaps: 1

References

Insertion Sort (Wikipedia)