Insertion sort: Difference between revisions

Revision as of 19:32, 31 July 2025

Revision as of 07:18, 1 August 2025

Line 166:

}}</ref>

To avoid having to make a series of swaps for each insertion, the input could be stored in a [[linked list]], which allows elements to be spliced into or out of the list in constant time when the position in the list is known.<!-- Troubling statement when insert/delete is used. The typical insertion and deletion operations take O(n) if position is not known. The O(1) operations are cons/splice/rplacd. --> However, searching a linked list requires sequentially following the links from each element to the desirednext (or previous) positionelement: a linked list does not have [[random access]], so it cannot use a faster method such as binary search to find the insertion point for an unsorted element. Therefore, the running time required for searching is O(''n''), and the time for sorting is O(''n''²).<!-- Instead of search, a max operation is more appropriate. --> If a more sophisticated [[data structure]] (e.g., [[heap (data structure)|heap]] or [[binary tree]]) is used, the time required for searching and insertion can be reduced significantly; this is the essence of [[heap sort]] and [[binary tree sort]].

In 2006 Bender, [[Martin Farach-Colton]], and Mosteiro published a new variant of insertion sort called ''[[library sort]]'' or ''gapped insertion sort'' that leaves a small number of unused spaces (i.e., "gaps") spread throughout the array. The benefit is that insertions need only shift elements over until a gap is reached. The authors show that this sorting algorithm runs [[with high probability]] in {{nowrap|O(''n'' log ''n'')}} time.<ref>{{cite journal