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: 6029
Venue: SIGMOD
Year: 2020
Pagerank: 7.0621718e-05
Overall Rank: 3,865 | 73.49%
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 16 of 16 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,061	Are We Ready For Learned Cardinality Estimation?	2021	VLDB	0.00012369764
1,551	Updatable Learned Index with Precise Positions	2021	VLDB	0.00010381398
2,919	SNARF: A Learning-Enhanced Range Filter	2022	VLDB	7.9628657e-05
5,148	LSched: A Workload-Aware Learned Query Scheduler for Analytical Database Systems	2022	SIGMOD	6.3465986e-05
5,974	Towards instance-optimized data systems	2021	VLDB	6.0230488e-05
6,590	MOST: Model-Based Compression with Outlier Storage for Time Series Data	2023	SIGMOD	5.8316635e-05
7,224	LITS: An Optimized Learned Index for Strings	2024	VLDB	5.6675134e-05
7,846	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.5331459e-05
8,234	The Case for Learned In-Memory Joins	2023	VLDB	5.460955e-05
8,791	HAP: An Efficient Hamming Space Index Based on Augmented Pigeonhole Principle	2022	SIGMOD	5.3717005e-05
9,411	Can Learned Indexes be Built Efficiently? A Deep Dive into Sampling Trade-offs	2024	SIGMOD	5.274743e-05
9,881	The Image Calculator: 10x Faster Image-AI Inference by Replacing JPEG with Self-designing Storage Format	2024	SIGMOD	5.2040783e-05
10,378	High Performance or Low Memory? An Updatable Learned Index Framework for Time-Space Tradeoff	2026	SIGMOD	5.093636e-05
10,505	The Case For Language Model Approximated LIKE Predicate	2026	SIGMOD	5.093636e-05
11,679	Efficient String Sort with Multi-Character Encoding and Adaptive Sampling	2021	SIGMOD	5.093636e-05
11,702	LES3: Learning-based Exact Set Similarity Search	2021	VLDB	5.093636e-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
43	The Case for Learned Index Structures	2018	SIGMOD	0.00046060254
84	Learned Cardinalities: Estimating Correlated Joins with Deep Learning	2019	CIDR	0.00035838391
154	Neo: A Learned Query Optimizer	2019	VLDB	0.00028726181
252	Multi-Core, Main-Memory Joins: Sort vs. Hash Revisited	2014	VLDB	0.00023242719
447	ALEX: An Updatable Adaptive Learned Index	2020	SIGMOD	0.00018322593
568	SageDB: A Learned Database System	2019	CIDR	0.0001641553
678	Fast Sort on CPUs and GPUs: A Case for Bandwidth Oblivious SIMD Sort	2010	SIGMOD	0.00015061068
790	FITing-Tree: A Data-aware Index Structure	2019	SIGMOD	0.0001401445
1,468	Towards a Learning Optimizer for Shared Clouds	2019	VLDB	0.00010686496
2,222	Efficiently Searching In-Memory Sorted Arrays: Revenge of the Interpolation Search?	2019	SIGMOD	8.9255716e-05
4,021	PARADIS: An Efficient Parallel Algorithm for In-place Radix Sort	2015	VLDB	6.9501893e-05
4,177	SIMD- and Cache-Friendly Algorithm for Sorting an Array of Structures	2015	VLDB	6.8499317e-05

Semantically Similar Papers

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