Simple and Fast BlockQuicksort using Lomuto's Partitioning Scheme

Martin Aumüller, Nikolaj Hass

Research output: Conference Article in Proceeding or Book/Report chapterArticle in proceedingsResearchpeer-review

Abstract

This paper presents simple variants of the BlockQuicksort algorithm described by Edelkamp and Weiss (ESA 2016). The simplification is achieved by using Lomuto's partitioning scheme instead of Hoare's crossing pointer technique to partition the input. To achieve a robust sorting algorithm that works well on many different input types, the paper introduces a novel two-pivot variant of Lomuto's partitioning scheme. A surprisingly simple twist to the generic two-pivot quicksort approach makes the algorithm robust. The paper provides an analysis of the theoretical properties of the proposed algorithms and compares them to their competitors. The analysis shows that Lomuto-based approaches incur a higher average sorting cost than the Hoare-based approach of BlockQuicksort. Moreover, the analysis is particularly useful to reason about pivot choices that suit the two-pivot approach. An extensive experimental study shows that, despite their worse theoretical behavior, the simpler variants perform as well as the original version of BlockQuicksort.
Original languageEnglish
Title of host publication2019 Proceedings of the Twenty-First Workshop on Algorithm Engineering and Experiments (ALENEX)
Number of pages14
PublisherSociety for Industrial and Applied Mathematics
Publication date2019
ISBN (Electronic)978-1-61197-549-9
DOIs
Publication statusPublished - 2019

Fingerprint

Dive into the research topics of 'Simple and Fast BlockQuicksort using Lomuto's Partitioning Scheme'. Together they form a unique fingerprint.

Cite this