INSERTION SORT is O(n log n)

Michael A. Bender; Martín Farach-Colton; Miguel A. Mosteiro

doi:10.1007/s00224-005-1237-z

INSERTION SORT is O(n log n)

Michael A. Bender, Martín Farach-Colton, Miguel A. Mosteiro

Research output: Contribution to journal › Article › peer-review

Abstract

Traditional INSERTION SORT runs in O(n²) 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.

Original language	English (US)
Pages (from-to)	391-397
Number of pages	7
Journal	Theory of Computing Systems
Volume	39
Issue number	3
DOIs	https://doi.org/10.1007/s00224-005-1237-z
State	Published - Jun 2006

ASJC Scopus subject areas

Theoretical Computer Science
Computational Theory and Mathematics

Access to Document

10.1007/s00224-005-1237-z

Cite this

@article{ec89150210ce4afe9a091c47f4e9ecdd,

title = "INSERTION SORT is O(n log n)",

abstract = "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.",

author = "Bender, {Michael A.} and Mart{\'i}n Farach-Colton and Mosteiro, {Miguel A.}",

year = "2006",

month = jun,

doi = "10.1007/s00224-005-1237-z",

language = "English (US)",

volume = "39",

pages = "391--397",

journal = "Theory of Computing Systems",

issn = "1432-4350",

publisher = "Springer New York",

number = "3",

}

TY - JOUR

T1 - INSERTION SORT is O(n log n)

AU - Bender, Michael A.

AU - Farach-Colton, Martín

AU - Mosteiro, Miguel A.

PY - 2006/6

Y1 - 2006/6

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=33646490751&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=33646490751&partnerID=8YFLogxK

U2 - 10.1007/s00224-005-1237-z

DO - 10.1007/s00224-005-1237-z

M3 - Article

AN - SCOPUS:33646490751

SN - 1432-4350

VL - 39

SP - 391

EP - 397

JO - Theory of Computing Systems

JF - Theory of Computing Systems

IS - 3

ER -

INSERTION SORT is O(n log n)

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this