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.

Properties

  • 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)