Worst-Case Efficient Sorting with QuickMergesort

Stefan Edelkamp, Armin Weiß

TL;DR

This paper introduces "median-of-medians QuickMergesort" (MoMQuickMergesort), a novel sorting algorithm that achieves worst-case efficiency comparable to Mergesort while maintaining the average-case speed of Quicksort, and doing so in-place. This addresses a long-standing challenge in sorting: finding an algorithm that is both fast on average and guarantees good performance even in the worst-case, without requiring excessive extra memory.

What Problem Does This Paper Address?

Sorting is a fundamental computer science problem. While Quicksort is renowned for its excellent average-case performance, it suffers from a quadratic worst-case time complexity. Mergesort, on the other hand, offers a guaranteed O(n log n) worst-case performance but requires O(n) extra space, making it impractical for in-place sorting. Heapsort is an in-place alternative with O(n log n) worst-case guarantees, but it's known for its poor cache performance and is generally slower than Quicksort and even Mergesort. The goal of this paper is to bridge this gap by developing an in-place sorting algorithm that combines the speed of Quicksort with the worst-case guarantees of Mergesort, overcoming the limitations of existing solutions like Heapsort.

Methods

The core innovation is a variant of QuickMergesort that uses the "median-of-medians" algorithm for pivot selection. QuickMergesort itself is a hybrid approach where an array is partitioned around a pivot, and then one part is sorted using Mergesort (leveraging the other part as temporary space), while the other part is recursively sorted using QuickMergesort.

The key contributions are:

  • Median-of-medians QuickMergesort (MoMQuickMergesort): Instead of selecting a random pivot (which leads to Quicksort's worst-case), MoMQuickMergesort uses the median-of-medians algorithm to select a pivot that guarantees a more balanced partition. This prevents the quadratic worst-case scenario.
  • Adaptive Pivot Selection: The paper introduces an improvement to the median-of-medians algorithm where the pivot selection is adapted based on the desired rank k. This helps to reduce the constant factors in the worst-case analysis.
  • Undersampling: To further optimize the algorithm, they propose "undersampling," where the median-of-medians algorithm is applied to a smaller subset of the data (e.g., n/d elements instead of n). This reduces the overhead of the median-of-medians step while still providing sufficient pivot guarantees.
  • Reinhardt's Merging Procedure: They leverage an efficient in-place merging technique described by Reinhardt, which requires less temporary space than standard Mergesort, making the overall algorithm more space-efficient.

Datasets

Not discussed in the paper. The experiments use random permutations and specifically crafted "killer" sequences to simulate worst-case scenarios.

Key Insights and Ideas

  • Pivot Selection is Key: The paper strongly emphasizes that the choice of pivot is critical for achieving both average-case speed and worst-case guarantees. Random pivots are fast on average but risky, while median-of-medians is safe but can have a large constant factor.
  • "Good Enough" Pivots Suffice: A crucial observation is that the median-of-medians algorithm doesn't need to find the exact median. A pivot that is "not very far off the median" is sufficient to guarantee a good partition for QuickMergesort, allowing for optimizations like undersampling.
  • In-place Merging is Crucial: The use of advanced in-place merging techniques (like Reinhardt's) is essential for making the QuickMergesort framework truly space-efficient.
  • Hybridization for Practicality: The paper explores hybrid approaches, such as using MoMQuickMergesort as a "worst-case stopper" for Introsort (std::sort), demonstrating its practical utility in improving existing robust sorting algorithms.

Key Results

  • Theoretical Guarantees: MoMQuickMergesort achieves a worst-case comparison bound of O(n log n) with a linear term of at most 1.59n (for MQMS11/5).
  • Practical Performance: Experiments show that MoMQuickMergesort (specifically MQMS11/5) is significantly faster than Heapsort and competitive with standard library implementations like std::sort (Introsort), being only about 10% slower on average.
  • Worst-Case Simulation: Simulated worst-case scenarios show that MoMQuickMergesort performs only slightly worse than its average case, a significant improvement over standard Quicksort.
  • Hybrid Performance: Hybrid QuickMergesort and MoMQuickMergesort as a worst-case stopper for Introsort outperform standard std::sort on specific "killer" input permutations.

Limitations and Future Work

  • Constant Factors: While the theoretical bounds are good, the constant factors in the median-of-medians algorithm can be large. The paper's optimizations (undersampling, adaptive pivot selection) aim to mitigate this.
  • Tightness of Bounds: The authors note that it's unclear whether the theoretical worst-case bounds are tight for real-world inputs, as designing such inputs is challenging.
  • Future Work:
    • Investigating alternative sampling methods for pivot selection (e.g., median of nine).
  • Further optimizing merging procedures.
  • Exploring parallel implementations of MoMQuickMergesort, which presents a unique challenge due to the dependency between the Mergesort and QuickMergesort parts.
  • Using Insertion Sort for small subarrays to further improve performance.

Summary updated

Abstract

The two most prominent solutions for the sorting problem are Quicksort and Mergesort. While Quicksort is very fast on average, Mergesort additionally gives worst-case guarantees, but needs extra space for a linear number of elements. Worst-case efficient in-place sorting, however, remains a challenge: the standard solution, Heapsort, suffers from a bad cache behavior and is also not overly fast for in-cache instances. In this work we present median-of-medians QuickMergesort (MoMQuickMergesort), a new variant of QuickMergesort, which combines Quicksort with Mergesort allowing the latter to be implemented in place. Our new variant applies the median-of-medians algorithm for selecting pivots in order to circumvent the quadratic worst case. Indeed, we show that it uses at most $n \log n + 1.6n$ comparisons for $n$ large enough. We experimentally confirm the theoretical estimates and show that the new algorithm outperforms Heapsort by far and is only around 10% slower than Introsort (std::sort implementation of stdlibc++), which has a rather poor guarantee for the worst case. We also simulate the worst case, which is only around 10% slower than the average case. In particular, the new algorithm is a natural candidate to replace Heapsort as a worst-case stopper in Introsort.
BibTeX
@inproceedings{edelkamp2019worst,
  author = {Stefan Edelkamp and Armin Weiß},
  title = {{Worst-Case Efficient Sorting with QuickMergesort}},
  booktitle = {ALENEX},
  year = {2019},
  url = {https://openreview.net/forum?id=VfjqNejPw5j},
}
Figure