Summary

Insertion Sort is an intuitive, comparison-based algorithm that builds a final sorted array one element at a time. It works much like sorting a hand of playing cards: you iterate through the elements, picking up one at a time and inserting it into its correct position within the already-sorted part of the list.

How it Works

• Assume the first element is a sorted sub-array of size one.

• Pick the next unsorted element. This is your key.

• Compare the key with the elements in the sorted sub-array, moving from right to left.

• Shift all elements in the sorted sub-array that are greater than the key one position to the right. This opens up a gap.

• Insert the key into this gap. The sorted sub-array is now one element larger.

• Repeat this process until all elements have been inserted into the sorted sub-array.