Understanding insertion sort algorithm

The strategy from the earlier example (sorting a hand of cards by picking each new card and slotting it into the sorted portion on the left) could be used to create an algorithm. To explain this algorithm, we will take an array as an input list, but the same algorithm can be applied to any list data structure.

Algorithm

Like bubble and selection sorts, insertion sort conceptually divides the input array into two subarrays: a sorted subarray and an unsorted subarray. Initially, the first element of the array (the element at index 0) is considered sorted, since a single element list is trivially in order.

During each iteration, the algorithm takes the first element from the unsorted subarray and inserts it into its correct position within the sorted subarray. To do this, it compares the element with the elements in the sorted subarray, moving from right to left.

If the unsorted element is smaller than a sorted element, the sorted element is shifted one position to the right. This shifting continues until the correct position for the unsorted element is found, at which point it is inserted.