User Tools

Site Tools


This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revision Previous revision
Next revision
Previous revision
insertion_sort [2012/09/30 18:05]
insertion_sort [2015/02/02 08:28] (current)
Line 1: Line 1:
 ====== Insertion sort ====== ====== 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
 [algorithm insertion sort] [algorithm insertion sort]
insertion_sort.1349053537.txt.gz ยท Last modified: 2015/02/02 08:24 (external edit)