User Tools

Site Tools


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

Link to this comparison view

Next revision
Previous revision
insertion_sort [2012/09/01 12:26]
will created
insertion_sort [2015/02/02 08:28] (current)
Line 1: Line 1:
 +====== 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.1346527594.txt.gz ยท Last modified: 2015/02/02 08:24 (external edit)