User Tools

Site Tools

Insertion sort

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 $O(n^2)$ 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.


  • Stable
  • $O(1)$ space
  • $O(n^2)$ comparisons and swaps
  • Adaptive, $O(n)$ when nearly sorted

λ insertion_sort

insertion_sort.txt · Last modified: 2015/02/02 08:28 (external edit)