Content deleted Content added
BrainStack (talk | contribs) Link suggestions feature: 3 links added. |
Reverted 1 edit by Bertuildede (talk): No indication of notability or even the truth of the added statement |
||
| (2 intermediate revisions by 2 users not shown) | |||
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
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
| |||