Insertion Sort

Time complexity: O(n²)

Insertion sort is an efficient algorithm for sorting a small number of elements. Insertion sort is very efficient at sorting nearly sorted datasets, even if they’re huge.

Insertion sort is more efficient in practice than most other simple quadratic algorithms, such as selectionsort or bubble sort.

Insertion sort works the same way you would sort cards. Start with your left hand empty, and the cards on the table. You pull a card from the deck and find the correct position for the card by comparing it with each of the cards already in your left hand, starting at the right and moving to the left. At all times, the cards held in your left hand are sorted.