Engineering Faster Sorters for Small Sets of Items

Jasper Marianczuk

REVIEW 3 major objections 3 minor 10 references

Engineering Faster Sorters for Small Sets of Items

T0 review · 3 major / 3 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Sorting networks beat insertion sort by at least 25% for small sets.

desk verdict A careful engineering thesis whose central small-set speedup is real and survives the stress test, though the abstract overgeneralizes from uniform random data and post-hoc variant selection. read the letter →

arxiv 1908.08111 v1 pith:TTOQSBQD submitted 2019-08-21 cs.DS

Jasper Marianczuk This is my paper · ORCID

classification cs.DS MSC 68P1068W40

keywords sortingnetworksinsertionsortbranchmispredictionconditionalmovesbasecasesorterinstructioncachesamplequicksort

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper asks whether there is a faster way to sort small sets of items than insertion sort, which is the usual base case inside larger sorting algorithms. It answers yes for sets of 2 to 16 elements: sorting networks, implemented with conditional-move instructions so their fixed comparison sequence has no branch mispredictions, were faster than insertion sort by at least 25% and up to about 59% in experiments on random 64-bit keys. The practical catch is code size. When the networks are used as a base case inside quicksort or IPS4o, the gains mostly disappear on machines with a 32 KiB L1 instruction cache and only become visible on a machine with a 64 KiB cache, where the paper reports speedups of 6.4% and 9.2%. The paper also introduces Register Sample Sort, a branchless samplesort that keeps splitters in general-purpose registers and reduces medium-sized sets down to sizes a network can sort.

What carries the argument

The load-bearing object is the sorting network, a fixed, data-oblivious sequence of comparators that always executes the same comparisons. The paper turns each comparator into a branchless conditional move (`cmov`) using inline assembly, so the CPU never has to predict a branch and never pays a misprediction penalty. The second object is Register Sample Sort, a modification of Super Scalar Sample Sort that holds splitters in general-purpose registers instead of an array and uses a carry-flag trick to accumulate bucket indices without branches. This machinery removes branch mispredictions from the small-set sort itself, and the experiments show that its benefit is then limited by how much code the L1 instruction cache can hold when the networks are embedded in a larger sorter.

What would settle it

Rerun the continuous-sort benchmark on already-sorted, reverse-sorted, and duplicate-heavy arrays of sizes 2 to 16 and compare the best sorting network against the best insertion sort; any distribution where the network falls below 25% or loses would falsify the unqualified claim.

Watch

Extended reading notes

Core claim

The central discovery is that the reason insertion sort is slow on small random arrays is branch misprediction, and that a sorting network, whose comparisons are fixed in advance and compiled to conditional moves, removes that cost. In measurements across three machines comparing many conditional-swap implementations, the fastest network beat the fastest insertion sort for every array size from 2 to 16, with the gap between 25% and 59%. The same networks used as a base case inside quicksort gave only marginal gains on machines with 32 KiB L1 instruction caches and about 6.4% on the 64 KiB machine; Register Sample Sort as an IPS4o base case gave 9.2% on the 64 KiB machine but was slower or neutral on the 32 KiB machines.

Load-bearing premise

The headline 'at least 25%' claim is supported only by measurements on uniformly distributed random 64-bit keys; on nearly sorted, reverse-sorted, or duplicate-heavy data, insertion sort's branches become predictable and the network's advantage could shrink or reverse.

Editorial extensions

If this is right

For any array size between 2 and 16, the fastest sorting network measured is at least 25% faster than the fastest insertion sort variant under the random-key conditions tested.
On a machine with a 64 KiB L1 instruction cache, using a sorting network as quicksort's base-case sorter instead of insertion sort speeds up quicksort by about 6.4%.
On the same 64 KiB machine, Register Sample Sort as IPS4o's base-case sorter gives a 9.2% speedup over insertion sort.
On 32 KiB L1 instruction cache machines, quicksort gains drop to around 2% or less and Register Sample Sort fails to improve IPS4o, showing the instruction cache as the bottleneck.
Register Sample Sort handles base cases up to 256 elements by splitting them into network-sortable chunks of 16 or fewer, using three splitters held in registers.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

If the branch-prediction explanation is what carries the result, the 25% figure should shrink or disappear on already-sorted, reverse-sorted, or duplicate-heavy inputs; the paper does not test those distributions, so the unqualified claim should be read as specific to uniform random keys.
The instruction-cache penalty suggests that a code-size-aware network design, such as networks that share comparison subroutines or split their sequence across cache-friendly blocks, could recover most of the base-case benefit inside large sorters; smaller code size is exactly what the paper lists as future work.
For everyday library sorters running on 32 KiB caches, the practical lesson is that branchless small-set sorters are a niche tool: they shine for repeated independent small sorts, not as internal base cases.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Short version: solid engineering work, and the central claim holds up better than the stress-test note suggests. What is actually new: conditional-move sorting networks for 64-bit key/reference pairs, several inline-assembly swap variants, Register Sample Sort, and measured integration into quicksort and IPS4o. The benchmarking is careful—500 repetitions, three machines, perf_event cycle counts, warmup runs, permutation checks, and code on GitHub. The authors also credit Codish et al. properly as the source of the core branchless-network idea. Credit where due: the small-set speedup is credible, and the L1 instruction-cache explanation for why integration gains are modest is plausible and consistent with the data.

The soft spots are real but not fatal. All measurements use uniformly random 64-bit keys; insertion sort's branch behavior depends on input order, so the abstract's unqualified 'at least 25%' overstates generality. There are no error bars or variance tables, only boxplots for one representative size. The authors select the fastest among many network/swap variants after seeing the data, which inflates the headline; a fixed variant such as N Best 4CS drops below 25% at size 2 in the continuous benchmark. Tuning Register Sample Sort parameters on the same machines is a mild circularity for the integration claims.

On the stress-test note specifically: it does not hold up. Table 7's fastest network at size 2 is N Best CPr at 13.90 cycles, not 15.97, so against the fastest insertion sort POp (20.67) the speedup is about 33%, above 25%. The 'at least 25%' claim is supported if 'sorting networks' means choosing the best implementation per size; it is not supported for every individual implementation, and the paper should say so. The citation pattern looks fine, and the authors are honest about the mixed integration results.

Who this is for: experimental algorithms people and library implementers who care about base-case sorters. It deserves a serious referee, not a desk reject. A revision should add non-uniform input distributions, report variance, and pin down the comparison baseline—best network per size versus one chosen variant. I would not cite it in my own work soon, but I would read a revised version.

Referee Report

3 major / 3 minor

Summary. The paper examines whether sorting networks implemented with conditional moves can replace insertion sort as a base-case sorter for small sets (n=2..16). The core empirical claim, stated in the abstract and in Section 4.5, is that sorting networks outperform insertion sort by at least 25% for every array size between 2 and 16. The paper also reports that integrating sorting networks into quicksort gives a 6.4% speedup on a machine with a 64 KiB L1 instruction cache, and that Register Sample Sort, a register-based variant of Super Scalar Sample Sort, gives a 9.2% speedup when used as an IPS4o base case. The measurements use three machines, 500 repetitions per setting, cycle-accurate PERF_EVENT timing, warmup runs, and probabilistic permutation checks. The paper makes its code publicly available and reports detailed per-variant tables (Tables 3-7) and box plots.

Significance. If the headline claim were fully supported, the paper would provide a useful engineering result: branchless, data-oblivious conditional-swap networks can materially beat insertion sort for small random inputs, and the main obstacle to using them inside larger sorters is L1 instruction-cache pressure. The study is unusually careful for an empirical systems paper: it uses cycle-accurate counters, checks that outputs are sorted permutations, measures on three architectures, and reports all variants rather than only the winners. The Register Sample Sort design, which holds splitters in registers and uses carry-flag tricks for branchless classification, is a real contribution. The significance is moderate: the standalone claim is a concrete quantitative benchmark result, but its scope is narrower than the abstract implies, and one of the paper's own tables does not support the stated 25% lower bound as written.

major comments (3)

[Section 4.5, Table 7] The text in Section 4.5 states that speed-ups range 'from 25% at array size 2', and the abstract repeats 'at least 25% for any array size between 2 and 16'. Table 7, which is the basis of that claim, does not support it if 'insertion sort' means the fastest insertion-sort variant. At array size 2 the fastest insertion variant is I -I KR POp at 20.67 cycles per array, and the fastest sorting networks (N Best -I KR 4CS, 4Cm, and 6Cm) all take 15.97 cycles. The speedup is (20.67 - 15.97) / 20.67 = 22.7%, not 25%. The 25% figure only holds when comparing against the slower I -I KR Def variant (22.17 cycles), which gives 28.0%. Since POp is the fastest insertion variant in both Table 6 and Table 7, the claimed lower bound needs to be either recomputed or explicitly qualified as comparing against a particular insertion-sort implementation rather than the fastest one.
[Section 4.3, Random Numbers; Tables 6-7] The measurements use only uniformly distributed random 64-bit keys, as stated in Section 4.3, yet the abstract's 'at least 25%' claim is unqualified. The mechanism behind the networks' advantage is branch misprediction on random data: insertion sort's inner branches are unpredictable when comparisons are 50/50, but on nearly sorted, reverse-sorted, or duplicate-heavy inputs those branches become highly predictable and the advantage of branchless networks can shrink or even reverse. A concrete test would be to repeat the continuous-sorting benchmark of Section 4.5 for sorted, reverse-sorted, and low-cardinality inputs and report the resulting speedups, or to restrict the claim explicitly to the uniform-random distribution used.
[Sections 4.7-4.8, Tables 9-10] The integrated speedups for Register Sample Sort and IPS4o are reported for configurations chosen after inspecting measurements on the same three machines (for example, oversampling factor and blockSize in Section 4.7, and the 16_331 configuration in Table 10). This is a form of in-sample selection: the paper does not validate the chosen configuration on held-out machines or with a validation protocol. I do not regard this as a fatal flaw for an engineering study, but the abstract and conclusion should state that the 6.4% and 9.2% figures are for per-machine best configurations, not for a configuration selected before the experiments.

minor comments (3)

[Section 4.2] The sentence 'The box incloses all values between the first quartile and third quartile' contains a typo; 'incloses' should be 'encloses'.
[Algorithm 1, Section 3.2] The pseudocode in Algorithm 1 contains an explicit branch ('if predicateResult > 0') and an explicit shift-add for the bucket index, while the surrounding text describes a branchless implementation using cmovc and rcl. Please add a sentence clarifying that the pseudocode is a logical description and that the assembly implementation avoids the branch.
[Figure 14, Machine C] The legend of Figure 16 labels the reference insertion-sort variant as 'I -Q KR POp' while the other figures use 'I -Q KR Def' as the reference; for consistency, state explicitly which variant is used for normalization in each plot.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the central claims are direct empirical benchmarks against external baselines.

full rationale

The paper's central claims are measurements: sorting networks outperform insertion sort on small sets, and using them as base cases yields modest speedups in quicksort and IPS4o. These are benchmark results comparing independently implemented sorters, not quantities derived from the claims themselves. The sorting networks are taken from external sources (Gamble's length-optimal networks and Bose-Nelson constructions), and the insertion sort, std::sort, and IPS4o baselines are external or previously published algorithms. The Register Sample Sort design is a modified Super Scalar Sample Sort, and its evaluation is again an empirical comparison, not a derivation that assumes its own conclusion. Some cited works involve the thesis supervisor, but those citations provide baseline algorithms and prior techniques; they are not used to justify the speedup numbers. Parameter choices such as oversampling factor, block size, and the post-hoc selection of the fastest network variant affect robustness and generality, but they do not make the reported improvements circular, because the results remain measured outcomes rather than predictions forced by construction.

Assumptions & free parameters 4 free parameters · 4 assumptions · 0 invented entities

No new physical entities are introduced. The central small-set result is a direct empirical comparison with no fitted constants. Tuning parameters appear only for the auxiliary Register Sample Sort and IPS4o configurations, and the headline 'best' numbers are selected post hoc from many variants.

free parameters (4)

oversampling factor for Register Sample Sort = 3 on all three machines (best in Section 4.7)
Chosen from measurements; affects sample-sort speed but not the standalone network claim.
blockSize for Register Sample Sort = 2 on machines A/B, 4 on machine C
Selected based on measured performance; shows machine-dependent tuning.
number of splitters for Register Sample Sort = 3
Fixed in Section 3.2 because 7 splitters would require too many registers; a design choice, not a measured fit.
IPS4o BaseCaseSize4 = 16, 32, and 64 tested
Varied in Section 4.8 to give Register Sample Sort larger base cases.

assumptions (4)

domain assumption Uniformly distributed random 64-bit keys are representative of small-set sorting workloads.
Underlies the central 'at least 25%' claim; all measurements in Sections 4.3-4.5 use this distribution.
domain assumption x86-64 conditional-move instructions execute without branch mispredictions and with the timing the author assumes.
The central mechanism, stated in Section 2.1.3 and used in the inline-assembly swap variants.
domain assumption The external sorting networks from Gamble and the Bose-Nelson generator are correct for sizes 2 to 16.
Networks are taken from external sources (Section 2.2.1) and used as given.
domain assumption Measured CPU-cycle differences are attributable to the sorting code, not to the measurement harness.
Algorithm 2 subtracts generation/checking time; the thesis notes negative times can occur for small sizes, indicating harness noise.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Engineering Faster Sorters for Small Sets of Items." pith.science (2026). https://pith.science/paper/TTOQSBQD

@misc{pith2026190808111,
  author       = {Pith},
  title        = {Pith review of: Engineering Faster Sorters for Small Sets of Items},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/TTOQSBQD}},
  note         = {Machine review of arXiv:1908.08111}
}

read the original abstract

Sorting a set of items is a task that can be useful by itself or as a building block for more complex operations. The more sophisticated and fast sorting algorithms become asymptotically, the less efficient they are for small sets of items due to large constant factor. This thesis aims to determine if there is a faster way to sort base case sizes than using insertion sort. For that we looked at sorting networks and how to implement them efficiently. Because sorting networks need to be implemented explicitly for each input size, providing networks for larger sizes becomess less efficient. That is why we modified Super Scalar Sample Sort to break down larger sets into sizes that can in turn be sorted by sorting networks. We show that the task of sorting only small sets can be greatly improved by at least 25% when using sorting networks compared to insertion sort, but that when integrating them into other sorting algorithms the speed-up is hindered by the limited L1 instruction cache size. On a machine with 64KiB of L1 instruction cache we achieved over 6% of improvement when using sorting networks as a base case sorter instead of insertion sort.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

10 extracted references · 9 canonical work pages

[1]

In: 25th Annual European Symposium on Algorithms, ESA 2017, September 4-6, 2017, Vienna, Austria

Axtmann , Michael ; Witt , Sascha ; Ferizovic , Daniel ; Sanders , Peter: In-Place Parallel Super Scalar Samplesort (IPSSSSo). In: 25th Annual European Symposium on Algorithms, ESA 2017, September 4-6, 2017, Vienna, Austria . https://github.com/SaschaWitt/ips4o, 2017, 9:1--9:14

work page 2017
[2]

Batcher , Kenneth E.: Sorting Networks and Their Applications. In: American Federation of Information Processing Societies: AFIPS Conference Proceedings: 1968 Spring Joint Computer Conference, Atlantic City, NJ, USA, 30 April - 2 May 1968 , 1968, 307--314

work page 1968
[3]

https://github.com/bertdobbelaere/SorterHunter, 2018

Bertdobbelaere : SorterHunter. https://github.com/bertdobbelaere/SorterHunter, 2018

work page 2018
[4]

Bose , R. C. ; Nelson , R. J.: A Sorting Problem. In: J. ACM 9 (1962), Nr. 2, 282--296. http://dx.doi.org/10.1145/321119.321126. -- DOI 10.1145/321119.321126

work page arXiv 1962
[5]

In: 26th IEEE International Conference on Tools with Artificial Intelligence, ICTAI 2014, Limassol, Cyprus, November 10-12, 2014 , 2014, 186--193

Codish , Michael ; Cruz - Filipe , Lu \' s ; Frank , Michael ; Schneider - Kamp , Peter: Twenty-Five Comparators Is Optimal When Sorting Nine Inputs (and Twenty-Nine for Ten). In: 26th IEEE International Conference on Tools with Artificial Intelligence, ICTAI 2014, Limassol, Cyprus, November 10-12, 2014 , 2014, 186--193

work page 2014
[6]

In: Formal Asp

Codish , Michael ; Cruz - Filipe , Lu \' s ; Nebel , Markus ; Schneider - Kamp , Peter: Optimizing sorting algorithms by using sorting networks. In: Formal Asp. Comput. 29 (2017), Nr. 3, 559--579. http://dx.doi.org/10.1007/s00165-016-0401-3. -- DOI 10.1007/s00165--016--0401--3

work page doi:10.1007/s00165-016-0401-3 2017
[7]

https://gcc.gnu.org/onlinedocs/gcc/Using-Assembly-Language-with-C.html, 2019

Free Software Foundation : How to Use Inline Assembly Language in C Code. https://gcc.gnu.org/onlinedocs/gcc/Using-Assembly-Language-with-C.html, 2019

work page 2019
[8]

http://pages.ripco.net/ jgamble/nw.html, 2019

Gamble , John M.: Sorting network generator. http://pages.ripco.net/ jgamble/nw.html, 2019

work page 2019

Show all 10 references

[9]

Addison-Wesley, 1998 http://www.worldcat.org/oclc/312994415

Knuth , Donald E.: The art of computer programming, , Volume III, 2nd Edition. Addison-Wesley, 1998 http://www.worldcat.org/oclc/312994415. -- ISBN 0201896850

1998
[10]

In: Algorithms - ESA 2004, 12th Annual European Symposium, Bergen, Norway, September 14-17, 2004, Proceedings , 2004, 784--796

Sanders , Peter ; Winkel , Sebastian: Super Scalar Sample Sort. In: Algorithms - ESA 2004, 12th Annual European Symposium, Bergen, Norway, September 14-17, 2004, Proceedings , 2004, 784--796

2004

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.

[1] [1]

In: 25th Annual European Symposium on Algorithms, ESA 2017, September 4-6, 2017, Vienna, Austria

Axtmann , Michael ; Witt , Sascha ; Ferizovic , Daniel ; Sanders , Peter: In-Place Parallel Super Scalar Samplesort (IPSSSSo). In: 25th Annual European Symposium on Algorithms, ESA 2017, September 4-6, 2017, Vienna, Austria . https://github.com/SaschaWitt/ips4o, 2017, 9:1--9:14

work page 2017

[2] [2]

Batcher , Kenneth E.: Sorting Networks and Their Applications. In: American Federation of Information Processing Societies: AFIPS Conference Proceedings: 1968 Spring Joint Computer Conference, Atlantic City, NJ, USA, 30 April - 2 May 1968 , 1968, 307--314

work page 1968

[3] [3]

https://github.com/bertdobbelaere/SorterHunter, 2018

Bertdobbelaere : SorterHunter. https://github.com/bertdobbelaere/SorterHunter, 2018

work page 2018

[4] [4]

Bose , R. C. ; Nelson , R. J.: A Sorting Problem. In: J. ACM 9 (1962), Nr. 2, 282--296. http://dx.doi.org/10.1145/321119.321126. -- DOI 10.1145/321119.321126

work page arXiv 1962

[5] [5]

In: 26th IEEE International Conference on Tools with Artificial Intelligence, ICTAI 2014, Limassol, Cyprus, November 10-12, 2014 , 2014, 186--193

Codish , Michael ; Cruz - Filipe , Lu \' s ; Frank , Michael ; Schneider - Kamp , Peter: Twenty-Five Comparators Is Optimal When Sorting Nine Inputs (and Twenty-Nine for Ten). In: 26th IEEE International Conference on Tools with Artificial Intelligence, ICTAI 2014, Limassol, Cyprus, November 10-12, 2014 , 2014, 186--193

work page 2014

[6] [6]

In: Formal Asp

Codish , Michael ; Cruz - Filipe , Lu \' s ; Nebel , Markus ; Schneider - Kamp , Peter: Optimizing sorting algorithms by using sorting networks. In: Formal Asp. Comput. 29 (2017), Nr. 3, 559--579. http://dx.doi.org/10.1007/s00165-016-0401-3. -- DOI 10.1007/s00165--016--0401--3

work page doi:10.1007/s00165-016-0401-3 2017

[7] [7]

https://gcc.gnu.org/onlinedocs/gcc/Using-Assembly-Language-with-C.html, 2019

Free Software Foundation : How to Use Inline Assembly Language in C Code. https://gcc.gnu.org/onlinedocs/gcc/Using-Assembly-Language-with-C.html, 2019

work page 2019

[8] [8]

http://pages.ripco.net/ jgamble/nw.html, 2019

Gamble , John M.: Sorting network generator. http://pages.ripco.net/ jgamble/nw.html, 2019

work page 2019