Mordecai J. Golin, Robert Sedgewick

Research output: Contribution to journalArticlepeer-review

10 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