Simple in-place yet comparison-optimal Mergesort
Christian Siebert · 2025
Read Simple in-place yet comparison-optimal Mergesort by Christian Siebert (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-24540.txt.
Introduction
Mergesort is fast and stable, but it needs a second array, which doubles memory and can rule it out for huge data. Christian Siebert proposes an in-place mergesort that is stable by design. Earlier in-place versions were mostly slow, unstable, or too complex to use in practice, he notes.
His algorithm rests on two parts: an optimal array rotation and the co-ranking idea from parallel mergesort work. It uses the optimal number of comparisons and runs with low constants in tests, including runs on one of the largest shared-memory machines available. Total time is a log factor above optimal, yet the method stays simple enough to teach and to ship.
Catalog record
| CREATOR | Christian Siebert |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 46 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2509-24540
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Simple in-place yet comparison-optimal Mergesort Christian Siebert Abstract Mergesort is one of the few efficient sorting algorithms and, despite being the oldest one, often still the method of choice today. In contrast to some alternative algorithms, it always runs efficiently using 𝒪 ( n log n ) \mathcal{O}(n\log n) element comparisons and usually works in a stable manner. Its only practical disadvantage is the need for a second array, and thus twice the amount of memory. This can be an impeding factor, especially when handling large amounts of data, where it is often either impractical or even impossible to fall back to slower or unstable sorting alternatives. Therefore, many attempts have been made to fix this problem by adapting Mergesort to work in place . While it is known that such algorithms exist, the previously published solutions are mostly not efficient, become unstable, and/or are very complex. This renders them practically useless for real-world applications. In this paper, we propose a novel in-place Mergesort algorithm that is stable by design. Albeit its running time of 𝒪 ( n log 2 n ) \mathcal{O}(n\log^{2}n) is not quite optimal, it still works efficiently, both in theory using the optimal number of 𝒪 ( n log n ) \mathcal{O}(n\log n) comparisons and in practice with low constants, while being easily comprehensible. The baseline for this new algorithm includes just two prerequisites: 1) an optimal array rotation; and 2) the co-ranking idea, published in 2014 and originally intended to parallelize Mergesort . Although it would certainly be possible to parallelize the presented algorithm, this paper focuses on the sequential aspect of this efficient, stable and in-place Mergesort algorithm. Additionally, we implemented our algorithm and present performance results measured on one of the largest shared memory systems currently available. University of Stuttgart, High-Performance Computing Center Stuttgart, [email protected]://orcid.org/0009-0009-8382-7487 ccs Theory of computation Sorting and searching ccs Theory of computation Complexity classes keywords Sorting Algorithm, Mergesort, Co-ranking, in-place, stable † † runningauthor: C. Siebert † † copyright: Christian Siebert † † event-title: This publication was submitted to ESA 2024, to SOSA ’25 and again to ESA 2025, but got rejected all the time † † event-shorttitle: Siebert 2025 † † event-acronym: Siebert † † year: 2025 † † event-date: December 24–27, 2016 † † event-location: Little Whinging, United Kingdom † † series-volume: 42 † † articleno: 23 1 Introduction Sorting is one of the most fundamental problems in computer science and is used in many applications. A sorting algorithm brings a given set of elements into a specified order. W.l.o.g., we are concentrating on data structures that allow random access to their elements, such as simple arrays. In the following, such arrays are depicted, for example, as A[0\dots n-1] , where A is the name of the array containing all elements, and 0 as well as n-1 are the lower and upper bounds—both inclusive—of element entries, meaning the number of elements in this array is n=|A| . Although there are very specialized sorting algorithms restricting its use, for example, to small element types (e.g., radix sort ), we consider the generic and unrestricted case based on comparisons. In such comparison-based sorting algorithms the order of elements is specified using a comparison operator, which takes two elements as input, compares their respective keys, and returns whether the first element either precedes \prec or succeeds \succ the second element, or if both have identical keys = , i.e., they are equal. For example, in the standard C library, this comparison operator is a function that uses a return value of type integer to encode these three options. As such, a valid comparison function can return -1, 1, and 0, respectively. This would also define the sorting order to be ascending. On the other hand, a descending order can be achieved by instead returning 1, -1, and 0, respectively. Two further terms that are necessary for the basic understanding of this paper are stability and rank. A sorting algorithm is said to be stable if elements with equal keys stay in the same relative order during sorting. The rank of an element corresponds to the unique index of this element if all elements have been sorted in a stable manner. It is well known that any comparison-based sorting algorithm needs \Omega(n\log n) comparisons in the worst case (see, e.g., [ 5 ] , p. 193). As such, we are, in particular when handling large amounts of data, mostly interested in sorting algorithms that usually achieve this theoretical lower bound. While there are many different sorting algorithms, only a few of them are appropriate in this context. For instance, the corresponding Wikipedia page [ 4 ] currently lists, explains and compares more than 45 different sorting algorithms, whereas the interesting ones for large n are represented by Quicksort , Mergesort and Heapsort . These three can also be varied and combined. Table 1 compares the aforementioned major algorithms with respect to their properties and features, marking these either with a thumbs-up if this is considered good or with a thumbs-down if not. In addition to the theoretical performance, we compare also the practical constant factor, which is ignored in the theoretical \mathcal{O} -notation. This constant can be obtained for a specific implementation and architecture by measuring its running time for different numbers of elements and fitting the resulting performance data to the formula c\cdot n\log n . Algorithm \sharp Comparisons Constant Stability Memory Quicksort \mathcal{O}(n^{2}) small unstable \mathcal{O}(\log n) Mergesort \mathcal{O}(n\log n) small stable \mathcal{O}(n) Heapsort \mathcal{O}(n\log n) large unstable \mathcal{O}(1) Table 1: Properties and features of “fast” sorting algorithms For example, Quicksort is popular because it has, in practice, a small hidden constant in the theoretical \mathcal{O} -notation and achieves \mathcal{O}(n\log n) comparisons in many cases, such as on average whenever pivots are picked at random. However, if unsuited pivot values are chosen (e.g., with fixed pivots and pre-sorted inputs), it can slow down to as low as \mathcal{O}(n^{2}) , which is catastrophic for large n . Heapsort , on the other hand, always achieves \mathcal{O}(n\log n) comparisons and needs no additional memory but is cache-inefficient and thus results in larger practical constants. Additionally, both of these sorting algorithms do not preserve the order of equal elements, so they are not stable. Although Mergesort meets this stability criterion and is efficient, it works wastefully regarding additional memory. In essence, an application programmer can only pick up to three good features out of the four compared properties and hence has to decide which sorting algorithm is best suited for a specific application. While there are attempts to improve upon certain disadvantages, such as improved pivot-selection strategies for Quicksort or reintroducing stability, this usually worsens one or more of the other properties. For example, every sorting algorithm can be turned into a stable sort by adding the original index to each element and comparing also the indices for equal elements. However, this will directly lead to an additional memory consumption of \mathcal{O}(n) . This paper concentrates on making Mergesort memory efficient, which is described by the algorithmic term in-place . A formal definition of this term will be given in Definition 3.2 .