Queue-mergesort

Mordecai J. Golin, Robert Sedgewick

Research output: Contribution to journalArticle

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

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

  • Cite this