Superscalar mergesort
2026-03-31
Note. To read this, you should be somewhat familiar with the comparison-based sorting model.
At the start of this year, I had been exploring ways to boost performance of a scalar mergesort (toward a fast, generic, and reliable sorting algorithm). At least for simple sorting tasks like sorting integer keys with single-instruction comparisons, quicksorts tend to be much faster since the difference in comparisons doesnβt particularly matter.
If youβre impatient, check out the repo. I guess.
Motivation
Traditional mergesorts are stable and out of place. I wanted an unstable in-place mergesort (similar properties to your average quicksort). We can consider space to be in-place. One benefit of mergesort is that its variants are generally less sensitive to patterns than quicksorts, which you likely know as everyone loves reciting that worst-case bound.
Making it fast
Mergesort has the advantage over quicksort that we can choose subarray sizes and merge, whereas quicksort partitions and gives you the sizes. We can cleanly target instruction level parallelism by overlapping two merges of the same size.
Reducing register pressure
If we want to target ILP, weβll have to address some issues. For a regular merge, we need to track 5 pointers: the endpoints of each subarray and the output. As the merging pointers advance (starting at the left), we need to check that they do not cross the guard pointers. We are broke on registers if we try to overlap two merges.

An interesting trick is that we can reverse the right subarray and use the same guard pointer for both subarrays, reducing bookkeeping to 4 pointers.

Now, letβs exploit the lack of required stability. We can entirely drop the guard pointer: even when one pointer crosses over, all subsequent merge steps yield correct outputs (you can work the comparisons out in your head). Since this gives us a fully unguarded loop, we reap a minor improvement with loop unrolling, but we also need only 3 pointers now.

One size fits all
Next, consider overlapping this merge with another of the same size. We write the output in reverse to build a result of the same bitonic shape, giving the impression of merging two of these shapes into one.

Now, letβs check out the distances between each left/right pair of pointers as they move. Let this distance for all input subarrays be . Then, the merge outputs have distance .

Every iteration, one input pointer steps toward the other (distance decreases by ), and the output pointers both step toward each other (distance decreases by ). Obviously, so the output pairs remain at distance . We can drop all right pointers and recompute them when needed, so we need just 3 pointers and one integer which serves also as the loop counter.

In general, if we want to overlap merges, we need pointers and one integer. With the initial setup, we would have needed pointers. I found 4-way interleaving (with 6 pointers) to be rather fast with smaller types (primitives).
Making it in-place
Our algorithm is unstable, yet it seems like we need memory similar to traditional mergesort. Itβs hard to settle for this. Instead, we simply use internal buffering. Below, X denotes a βjunkβ item used as extra space.
X X X X X X X X
1 2 5 8 3 4 6 7Rather than overwrite to an output region while merging, we swap with the βjunkβ items.
1 2 3 4 5 6 7 8
X X X X X X X XThis technique is described in more detail in this sorting wiki page. Use that wiki for sorting information over Wikipedia.
Done!
I applied the merge algorithm to an in-place, unstable mergesort that creates the needed junk space mentioned above. I chose Proportion Extend Merge Sort by @aphitorite as the base algorithm for its very strong worst case performance. I believe there should be a paper about this method as well. Itβs also a good choice for adapting to runs in-place, which I might write about in the future. The one big issue with this algorithm is that it still needs partitioning, which one could pedantically argue results in an impure mergesort, but this is not really about theory (alternative mergesort frameworks may be used).
@2026 bzy.