Mordecai J. Golin, Robert Sedgewick

Research output: Contribution to journalArticlepeer-review

3 Scopus citations


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 languageEnglish (US)
Pages (from-to)253-259
Number of pages7
JournalInformation Processing Letters
Issue number5
StatePublished - Dec 10 1993

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Signal Processing
  • Information Systems
  • Computer Science Applications


  • Algorithms
  • Binary trees
  • Huffman encoding
  • Mergesort


Dive into the research topics of 'Queue-mergesort'. Together they form a unique fingerprint.

Cite this