Insertion sort is a simple sorting algorithm in which the sorted list is constructed one element at a time. The time complexity of selection sort is O(n²) for an array containing n elements. Thus, it is quite an inefficient means of sorting for large data sets. Nevertheless, it is a fairly intuitive algorithm, and it has certain benefits.

Insertion sort is a particularly useful when the data set is a small list of elements, and when memory is limited. Similar to Selection sort, it is considered an "in-place" algorithm, which means that no additional storage is needed to complete the sort. The sort is done within the array that holds the original list. The Algorithm: The array is partitioned into a sorted portion and an unsorted portion. We begin with the first element (at index i=0) a sorted sub array of length 1. Then we begin iterating through the unsorted portion array, placing each unsorted element in its correct place in the sorted portion of the array.

We place each next element in the unsorted array into the sorted portion by continually swapping with its left adjacent element until it’s left adjacent element has a value less than or equal to its own value. Once the last element in the unsorted portion is inserted into the sorted portion, we have the final sorted array.