Queue-mergesort

Mordecai J. Golin; Robert Sedgewick

doi:10.1016/0020-0190(93)90088-Q

Queue-mergesort

Mordecai J. Golin, Robert Sedgewick

Computer Science

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

11 Scopus citations

Abstract

Mergesort is one of the oldest and most venerable sorting algorithms and exists in many different flavors. In this short note we present yet another mergesort variant, queue-mergesort. We show that, like top-down mergesort but unlike bottom-up mergesort, this new variant performs an optimal number of comparisons in the worst case.

Original language	English (US)
Pages (from-to)	253-259
Number of pages	7
Journal	Information Processing Letters
Volume	48
Issue number	5
DOIs	https://doi.org/10.1016/0020-0190(93)90088-Q
State	Published - Dec 10 1993

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Signal Processing
Information Systems
Computer Science Applications

Keywords

Algorithms
Binary trees
Huffman encoding
Mergesort

Access to Document

10.1016/0020-0190(93)90088-Q

Cite this

@article{3b22d0a04b374e06b88c91cd39ec6964,

title = "Queue-mergesort",

abstract = "Mergesort is one of the oldest and most venerable sorting algorithms and exists in many different flavors. In this short note we present yet another mergesort variant, queue-mergesort. We show that, like top-down mergesort but unlike bottom-up mergesort, this new variant performs an optimal number of comparisons in the worst case.",

keywords = "Algorithms, Binary trees, Huffman encoding, Mergesort",

author = "Golin, \{Mordecai J.\} and Robert Sedgewick",

note = "Funding Information: * Corresponding author. This research was performed while the author was at Princeton University. It was supported by National Science Foundation grant DCR-8605962 and Office of Naval Research grant N00014-87-K-0460. * * This research was supported by National Science Foundation grant DCR-8605962 and Office of Naval Research grant N00014-87-K-0460.",

year = "1993",

month = dec,

day = "10",

doi = "10.1016/0020-0190(93)90088-Q",

language = "English (US)",

volume = "48",

pages = "253--259",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier B.V.",

number = "5",

}

TY - JOUR

T1 - Queue-mergesort

AU - Golin, Mordecai J.

AU - Sedgewick, Robert

N1 - Funding Information: * Corresponding author. This research was performed while the author was at Princeton University. It was supported by National Science Foundation grant DCR-8605962 and Office of Naval Research grant N00014-87-K-0460. * * This research was supported by National Science Foundation grant DCR-8605962 and Office of Naval Research grant N00014-87-K-0460.

PY - 1993/12/10

Y1 - 1993/12/10

N2 - Mergesort is one of the oldest and most venerable sorting algorithms and exists in many different flavors. In this short note we present yet another mergesort variant, queue-mergesort. We show that, like top-down mergesort but unlike bottom-up mergesort, this new variant performs an optimal number of comparisons in the worst case.

AB - Mergesort is one of the oldest and most venerable sorting algorithms and exists in many different flavors. In this short note we present yet another mergesort variant, queue-mergesort. We show that, like top-down mergesort but unlike bottom-up mergesort, this new variant performs an optimal number of comparisons in the worst case.

KW - Algorithms

KW - Binary trees

KW - Huffman encoding

KW - Mergesort

UR - https://www.scopus.com/pages/publications/0027887524

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

U2 - 10.1016/0020-0190(93)90088-Q

DO - 10.1016/0020-0190(93)90088-Q

M3 - Article

AN - SCOPUS:0027887524

SN - 0020-0190

VL - 48

SP - 253

EP - 259

JO - Information Processing Letters

JF - Information Processing Letters

IS - 5

ER -

Queue-mergesort

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this