Insertion Sort Algorithm Implementation In Python

It's a stable, in-place algorithm, that works really well for nearly-sorted or small arrays.

How Insertion Sort Works An array is partitioned into a "sorted" subarray and an "unsorted" subarray. At the beginning, the sorted subarray contains only the first element of our original array.

The first element in the unsorted array is evaluated so that we can insert it into its proper place in the sorted subarray.

The insertion is done by moving all elements larger than the new element one position to the right.

Continue doing this until our entire array is sorted.