Insertion sort is the sorting mechanism where the sorted array is built one item at a time. The array elements are compared with each other sequentially and then arranged simultaneously in some particular order. It works similarly as we sort cards in our hand in a card game.
| Best | Average | Worst | Space (Memory) | Stable | Advantage |
|---|---|---|---|---|---|
| O(n) | O(n2) | O(n2) | O(1) | Yes | Efficient for data sets that are almost sorted list |