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

Both sides previous revision Previous revision Next revision | Previous revision | ||

insertion_sort [2012/09/30 18:05] will |
insertion_sort [2014/04/28 22:33] will |
||
---|---|---|---|

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.txt ยท Last modified: 2015/02/02 08:28 (external edit)