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

Computer Science

Rutgers - The State University of New Jersey, New Brunswick

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

46 Scopus citations

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

Access to Document

10.1007/s00224-005-1237-z

Cite this

@article{6ec11bdbe1b140e287efe631e5d087c0,

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",

volume = "39",

pages = "391--397",

journal = "Theory of Computing Systems",

issn = "1432-4350",

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 - https://www.scopus.com/pages/publications/33646490751

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

Access to Document

Other files and links

Fingerprint

Cite this