Nematrian Reference Library
[this page | back links]
Set out below is information (held by the Nematrian website) on the reference you have selected
| Reference | Title | Link |
| Bender, M.A, Farach-Colton, M. and Mosteiro, M. (2008 | Insertion Sort is O(n log n) | here |
Abstract
"Traditional INSERTION SORT runs in O(n^2) time because each insertion takes O(n) time. When people run INSERTION SORT in the physical world, they leave gaps between items to accelerate insertions. Gaps help in computers as well. This paper shows that GAPPED INSERTION SORT has insertion times of O(log n) with high probability, yielding a total running time of O(n log n) with high probability." |
See
here to choose a new Category/Sub-Category or
here for a list of all references held by the Nematrian website. Please
contact us if any of the above material is inaccurate or if there are references you think should be included that we have excluded or vice-versa.