Authors
Michael A Bender, Martin Farach-Colton, Miguel A Mosteiro
Publication date
2006/6
Journal
Theory of Computing systems
Volume
39
Pages
391-397
Publisher
Springer-Verlag
Description
Traditional Insertion Sort runs in O(n2) 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.
Total citations
2007200820092010201120122013201420152016201720182019202020212022202320242151453579108776936
Scholar articles
MA Bender, M Farach-Colton, MA Mosteiro - Theory of Computing systems, 2006
MA Bender, M Farach-Colton, AM Miguel - arXiv preprint cs.DS/0407003, 2004