Insertion sort is a simple sort algorithm that sorts a list by building a sorted list front to back. It repeatedly moves the next unsorted element towards the front of the list until it is in a sorted position. Although it has a worst case of it is often the algorithm of choice for small data sets or when the data is almost sorted due to its low overhead and that the algorithm is both stable and adaptive.

Properties

  • Stable
  • space
  • comparisons and swaps
  • Adaptive, when nearly sorted