PCF Learned Sort

This is the official implementation of our paper, PCF Learned Sort: a Learning Augmented Sort Algorithm with $\mathcal{O}(n \log\log n)$ Expected Complexity.

Abstract: Sorting is one of the most fundamental algorithms in computer science. Recently, Learned Sorts, which use machine learning to improve sorting speed, have attracted attention. While existing studies show that Learned Sort is empirically faster than classical sorting algorithms, they do not provide theoretical guarantees about its computational complexity. We propose Piecewise Constant Function (PCF) Learned Sort, a theoretically guaranteed Learned Sort algorithm. We prove that the expected complexity of PCF Learned Sort is $\mathcal{O}(n \log \log n)$ under mild assumptions on the data distribution. We also confirm empirically that PCF Learned Sort has a computational complexity of $\mathcal{O}(n \log \log n)$ on both synthetic and real datasets. This is the first study to theoretically support the empirical success of Learned Sort, and provides evidence for why Learned Sort is fast.

git clone --recursive [email protected]:atsukisato/PCF_Learned_Sort.git
cd PCF_Learned_Sort

./sh/download.sh

./sh/run_all.sh

This script will:

• Compile the source code
• Run experiments on synthetic/real/adversarial datasets
• Profile PCF Learned Sort
• Generate plots

All logs, profiling results, and generated figures will be automatically stored in result/.

• g++ (C++17 or later)
• make
• Python 3 (for plotting)

PCF_Learned_Sort/
├── bin/                     # Compiled executables
├── data/                    # Datasets
├── experiments/             # Experimental code
├── src/                     # Core algorithm implementation
├── sh/                      # Scripts for setup and evaluation
├── plot/                    # Python scripts to generate figures
├── result/                  # Generated figures and logs
├── Makefile
└── README.md

This project is licensed under the terms of the GNU General Public License v3.0. See the LICENSE file for details.

If you use PCF Learned Sort in your research, please cite our TMLR 2025 paper:

@article{sato2025pcflearnedsort,
    title={PCF Learned Sort: a Learning Augmented Sort Algorithm with $\mathcal{O}(n \log\log n)$ Expected Complexity},
    author={Sato, Atsuki and Matsui, Yusuke},
    journal={Transactions on Machine Learning Research},
    year={2025}
}