INSERTION SORT is O(n log n)

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

    Research output: Contribution to journalArticlepeer-review


    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.

    Original languageEnglish (US)
    Pages (from-to)391-397
    Number of pages7
    JournalTheory of Computing Systems
    Issue number3
    StatePublished - Jun 2006

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • Computational Theory and Mathematics


    Dive into the research topics of 'INSERTION SORT is O(n log n)'. Together they form a unique fingerprint.

    Cite this