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.
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Signal Processing
- Information Systems
- Computer Science Applications
- Binary trees
- Huffman encoding