The Case for a Learned Sorting Algorithm

Summary: A learned distribution sort maps keys to positions via a CDF model, then finishes with a near-sorted pass. Up to 1B doubles, normally distributed, it yields 3.38x STL, 1.49x Radix, 5.54x TimSort, showing learned sorting as a practical primitive. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: hd7c56708a07a1812
Venue: SIGMOD
Year: 2020
Pagerank: 7.0769061e-05
Overall Rank: 3,714 | 75.04%
DOI: 10.1145/3318464.3389752

Incoming Non-self Citations Over Time

Authors

1. Ani Kristo (Brown University)
2. Kapil Vaidya (Massachusetts Institute of Technology)
3. Uğur Çetintemel (Brown University)
4. Sanchit Misra (Intel)
5. Tim Kraska (Massachusetts Institute of Technology)

BibTeX Citation

@inproceedings{kristo_sigmod20,
        title = {{The Case for a Learned Sorting Algorithm}},
        author = {Kristo, Ani and Vaidya, Kapil and Çetintemel, Uğur and Misra, Sanchit and Kraska, Tim},
        series = {{SIGMOD} '20},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3318464.3389752},
        url = {https://dl.acm.org/doi/10.1145/3318464.3389752},
        year = {2020}
}

Incoming Citations (Sorted by Pagerank)

Showing 17 of 17 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,064	Are We Ready For Learned Cardinality Estimation?	2021	VLDB	0.00012202282
1,550	Updatable Learned Index with Precise Positions	2021	VLDB	0.00010282449
2,837	SNARF: A Learning-Enhanced Range Filter	2022	VLDB	7.9527715e-05
5,041	LSched: A Workload-Aware Learned Query Scheduler for Analytical Database Systems	2022	SIGMOD	6.3006152e-05
5,974	Towards instance-optimized data systems	2021	VLDB	5.9305575e-05
6,694	MOST: Model-Based Compression with Outlier Storage for Time Series Data	2023	SIGMOD	5.7068014e-05
7,372	LITS: An Optimized Learned Index for Strings	2024	VLDB	5.5403496e-05
7,977	The Holon Approach for Simultaneously Tuning Multiple Components in a Self-Driving Database Management System with Machine Learning via Synthesized Proto-Actions	2024	VLDB	5.4142519e-05
8,403	The Case for Learned In-Memory Joins	2023	VLDB	5.3389852e-05
8,946	HAP: An Efficient Hamming Space Index Based on Augmented Pigeonhole Principle	2022	SIGMOD	5.2532874e-05
9,593	Can Learned Indexes be Built Efficiently? A Deep Dive into Sampling Trade-offs	2024	SIGMOD	5.156392e-05
9,741	LES3: Learning-based Exact Set Similarity Search	2021	VLDB	5.1349531e-05
10,043	The Image Calculator: 10x Faster Image-AI Inference by Replacing JPEG with Self-designing Storage Format	2024	SIGMOD	5.0921006e-05
10,575	High Performance or Low Memory? An Updatable Learned Index Framework for Time-Space Tradeoff	2026	SIGMOD	4.9793485e-05
10,691	The Case For Language Model Approximated LIKE Predicate	2026	SIGMOD	4.9793485e-05
10,840	CrocSort: Resource-Efficient, Skew-Resilient Parallel External Merge Sort	2026	VLDB	4.9793485e-05
11,986	Efficient String Sort with Multi-Character Encoding and Adaptive Sampling	2021	SIGMOD	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 12 of 12 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
40	The Case for Learned Index Structures	2018	SIGMOD	0.00046284649
85	Learned Cardinalities: Estimating Correlated Joins with Deep Learning	2019	CIDR	0.00035864347
145	Neo: A Learned Query Optimizer	2019	VLDB	0.0002908188
251	Multi-Core, Main-Memory Joins: Sort vs. Hash Revisited	2014	VLDB	0.00023143736
430	ALEX: An Updatable Adaptive Learned Index	2020	SIGMOD	0.00018409112
555	SageDB: A Learned Database System	2019	CIDR	0.00016506678
661	Fast Sort on CPUs and GPUs: A Case for Bandwidth Oblivious SIMD Sort	2010	SIGMOD	0.00015003815
779	FITing-Tree: A Data-aware Index Structure	2019	SIGMOD	0.00014030069
1,433	Towards a Learning Optimizer for Shared Clouds	2019	VLDB	0.00010677711
2,236	Efficiently Searching In-Memory Sorted Arrays: Revenge of the Interpolation Search?	2019	SIGMOD	8.7776298e-05
4,065	PARADIS: An Efficient Parallel Algorithm for In-place Radix Sort	2015	VLDB	6.8227646e-05
4,225	SIMD- and Cache-Friendly Algorithm for Sorting an Array of Structures	2015	VLDB	6.7207703e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	7,854	A Study of Sort Algorithms for Multiprocessor Database Machines	1986	VLDB
2	722	Efficient Implementation of Sorting on Multi-Core SIMD CPU Architecture	2008	VLDB
3	848	Benchmarking Learned Indexes	2021	VLDB
4	1,116	A Comprehensive Study of Main-Memory Partitioning and its Application to Large-Scale Comparison- and Radix-Sort	2014	SIGMOD
5	6,829	Percentile Finding Algorithm for Multiple Sorted Runs	1989	VLDB
6	661	Fast Sort on CPUs and GPUs: A Case for Bandwidth Oblivious SIMD Sort	2010	SIGMOD
7	4,225	SIMD- and Cache-Friendly Algorithm for Sorting an Array of Structures	2015	VLDB
8	12,328	A Study of Sorting Algorithms on Approximate Memory	2016	SIGMOD
9	2,487	A Memory Bandwidth-Efficient Hybrid Radix Sort on GPUs	2017	SIGMOD
10	11,986	Efficient String Sort with Multi-Character Encoding and Adaptive Sampling	2021	SIGMOD