PCF Learned Sort: a Learning Augmented Sort Algorithm with $\mathcal{O}(n \log\log n)$ Expected Complexity
Authors: Atsuki Sato
Yusuke Matsui
Venue: Accepted by TMLR ()

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.

Published in Transactions on Machine Learning Research (10/2025)
PCF Learned Sort: a Learning Augmented Sort Algorithm with On log log n) Expected Complexity
Atsuki Sato
a_ watothaatt.tttoooo.oooo
Graduate School of Information. Science and Technology The University of Tokyo
Yusuke Matsui
malsui@hallLLa-ttkkee ac.ip
Gruduate School of Information Science and Technology The Universily of Tokyo
Reviewed on OpenReview: https: openreview. net/ formm? td=wVkb.BWHbul
Abstract
Sorting is of the most fundamental algorithms in computer science. Recently, Learned Sorts, which use machine learning to improve sorting speed, have attracted attention. While existing st uddees show that Learned Sort is empirically faster than classical sorting algorithms, they do not provide theoretical guarantees about its computational complexity. We propose Piccewise Constant Function (PCF) Learned Sort, a theoretically guaranteod Learned Sort algorithu. We prove that the expected complexity of PCF Learned Sort is O(n log log n) under mild assumptions on the data distrriuttio. We also confirm empirically that PCF Learned Sort has a computational complexity of O(n 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.
1 Introduction
Sorting is one of the most fundamental algorithms in computer science and has been extensively studied for many years. Recently, novel sorting method called Learned Sort has been proposed (Kraska et al. 2019). In Learned Sort, machine learning model is trained to estimate the distribution of elements in the input array, specifically, the cumulative distribution function (CDF). The model's predictions are then used to rearrange the elements, followed by a minor refinement step to complete the sorting process. Empirical results show that Learned Sort faster than classical sorting algorithms, including highly optimized counting-basod sorting algorithms, comparison sorting algorithms, and hybrid sorting algorithms.
On the other hand, there are few theoretical guarantees regarding the computational complexity of Learned Sort. The first proposed Learned Sort algorithm (Krakka et al.) 2019 has a best-case complexity of O(n), but its expected or worst-case complexity is not discussed. The more efficient Learned Sort algorithms proposed later (Kristo et al. 2020 2021a) also have (n)) best-case complexity, but O(n?) worst-case complexity (or O(n log n) with some modifications.. The goal of this paper is to develop a Learned Sort that theoretically guarantcod to be computationally efficient.
We propose Piecewise Constant Function (PCF) Learned Sort, which can sort with expected complexity On log n) under mild assumptions the data distribution. In addition, we show that PCF Learned Sort admits a worst-case complexity guarantee that depends on the choice of the internal sorting algorithm. For instance, if MergeSort- whose worst-case complexity is O(n log is used, then the worst-case complexity of PCF Learned Sort is O(n lognn. If we instead use the algorithm by Han (2020), which has a casst-case complexity of Onn n), then the worst-case complexity of PCF Learned Sort bocomes On n). We then empirically confirm that our Learned Sort can sort with a complexity of O(n log logn) on both synthetic and real datasets.

---

Published in Transactions on Machine Learning Research (10/2025)
Independently and concurrently, Zeighami & Shahabi (024) explored complexity-guarantee Learned Sort. While our PCF Learned Sort is motivated by similar principles and incorporates comparable design choices, several key distinctions exist between our approach and theirs. A comprehensive comparison between our method and that of Zeighami & Shahabi (2024) is provided in Section
This paper organized as follows. Section 2 reviews related literature. Section g introduces PCF Learned Sort and provides complexity theorems with proof sketches. Section provides empirical validation of the theoretical results. We discuss implications and limitations in Section and conclude in Section 6
2 Related Work
Our research in the context of algorithms with machine learning (Section 2.1 There are two types of sorting algorithms, comparison sorts (Section 2.20 and non-comparison sorts (Section 2.30. and our proposed method is a non-comparison sort. However, the idea, implementation, and proof of computational complexity of our method are similar to those of sample sort, which is a type of comparison sort. Furthermore, our proposed algorithm and proof of computational complexity are based on those of Learned Index (Section 2.4
2.1 Algorithms with Machine Learning
Our work lies in the emerging area of Learned Sort, where machine learning models accelerate sorting. The first approach by Kraska et al. (2019) trained model F()) to approxinale the CDF F(y) and placed each element at position nF(x)) and then applies insertion sort to complete the ordering. While this yields ((n) in favorable cases, the insertion-based refinement causes a O(n²) worst case. Later implementations improved cache efficiency (Kristo et al.) 2020), robustness to duplicates (Kristo et al. 2021ab, and even introduced cache-friendly CDF models tailored for sorting (Ferragina & Odorisio 2025). but still relied on insertion sort and thus retained a quadratic worst-case complexity. Using stronger fallback algorithms such as Introsort (Musscr 1997) or TimSort (MeIlroy 1993) reduces this to O(n On log n), though this only matches classical comparison- based sorts and does not. fully explain the empirical advantage of Learned Sort.
Parallelization has also been explored: Carvalho (2022) proposed IPLS, integrating learned partitioning into IPS4o (Axtmann et al.) 2017), and Carvalho & Lawrence (2023) framed LearnedSort as a sample sort with a parallel TPS4o implementation. These studies primarily highlight the engineering polential of learned sorting in parallel settings, which is complementary but orthogonal our focus on providing theoretical guarantees
for the sequential case.
In broader context, Li et al. (2020) showed that neural programs can achieve strong generalization and replicate efficient algorithmic behaviors such as sorting, demonstrating that machine learning can recover algorithmic complexity classes like Onn log n) without explicit manual design. This provides a useful per- spective on the generalizability of learned algorithms.
Related to this, the field of algorithms with predictions studies how machine learning predictions accelerate classical algorithms (Mitzenmacher & Vassilvitskii 2022), with applications in caching ( (Narayanan el al.
2018 Rohatgi 2020 Lykouris & Vassilvitskii 2021 Im al. 2022 , ski rental (Purohit et al. 2018 Gollapudi
& Panigrahi 2019 Shin et al. 2023), scheduling GGolapudi & Panigrahi
2019 Lattanzi et al. 2020 Lassota
ct al. 2023) and matching (Antoniadis et al.) 2023 Dinitz et al. 2021 Sakane & Oki 2022).
Sorting with
predictions has also been analyzed (Lu et al. 2021 Chan et al. 2023 Frlebach et al. 2023 including
tight guarantees by Bai Coester (2023). In the context of algorithms with predictions, machine learning
predictions are typically assumedd to be available at no cost, and the models are treated as an opaque box.
This exclusion contrasts with our problem setting, where we ensure that the computational complexity covers the entire process from receiving unsorted array to returning sorted array.
2.2 Comparison Sorts
Sorting algorithms that use comparisons between keys and require no other information about the keys are called comparison sorts. It well-known that the worst-case complexity of a comparison sort is at least lognlogn) Commonly used comparison sorting algorithms include QuickSort, heap sort, merge sort.
2

---

Published in Transactions on Machine Learning Research (10/2025)
algo- rithm that combines QuickSort, heap sort, and insertion sort. Java (Java 2023 and Python up to version 3.10 (Peters 2002) use TimSort (Melhroy 1993), : an improved version of merge sort. Python 3.11 and later
and insertion sort. The GNU Standard Template Library in C++ uses Introsort Muusser 1997
use Powersort [Murro& & Wild 2018). a merge sort that determines a near-optimal merge order.
Sample sort (Frazer & McKellar 1970 extends QuickSort by using multiple pivots instead of one. Sample sort samples a small number of keys from the array, determines multiple pivots, and uses them parti- tion the array into multiple buckets. The partitioning is repeated recursively until the array is sufficiently small. Among its implementations, the in-place parallel superscalar sample sort (Axtmann et al. 2017 introduced as highly efficient parallel algorithm, and later engineering refinements further improved its performance (Axtmann et al. 2022). Its computational and cache efficiency is theoretically guaranteed by a theorem about the probability that the pivots partition the array (nearly) equally.
2.3 Non-Comparison Sorts
Non- Non-comparison sorts use information other than key comparison. Radix sort and counting sort are the most common types of non-comparison sorts. Radix sort uses counting sort as a subroutine for each digit. When the number of digits in the array element w, the computational complexity of radix sort (wm). Thus, radix sort is particularly effective when the number of digits is small. There are several variants of radix sort, such as Spreadsort (Ross) 2002), which integrates the advantages of comparison sort into radix sort and is implemented in the Boost C++ Libraries, and RegionSort (Obeya et al., 2019), which enables efficient parallelization by modeling and resolving dependencies among the element swaps.
In addition, non-comparison sorting algorithms tailored for specific data types have been developed. For integer arrays, a deterministic algorithm with worst-case complexity of OOn logn) (Han 2002 and a ran- domized algorithm with expected complexity of (ny/log n) (Han & Thorup 2002) have been proposed. For real-valued arrays, recent advances have led to the development of a sorting algorithm with a worst-case complexity of O(nylogg)) (Ham 2020). Our PCF Learned Sort also targets real-valued arrays and, under mild assumptions the distribution, achieves
expected complexity of O(n log log Moreover, when the algorithm of Han (2020) is used as the internal sorting component, PCF Learned Sort has a worst-case complexity of O Mog/logn, n),, which matches that of Han 2020
2.4 Learned Index
Kraska et al. 2018 showed that index data structures such as B-trees and Bloom filters can be made faster or more memory efficient by combining them with machine learning models and named such novel
data structures Learned Index. Since then, learning augmented B-trees (Wang et al.) 2020 Kipf et al. 2020
Ferragina & Vinciguerra 2020 Zeighami & Shahabi 2023). Bloom filters (Mitzenmacher 2018 Vaidya et al.
2021 Sato & Malsui 2023 2024), and even range-minimun query structures (Ferragina el. al.) 2025 have
been proposed. There are several works on learning augmented B-trees whose performance is theoretically guaranteed. PGM-index (Ferragina & Vinciguerra 2020) is a learning augmented B-tree that is guaranteed to have the same worst-case query complexity the classical B-tree, i.e., O(log Zeighami & Shahabi (2023) proposed a learning augmented B-tree with an expected query complexity of O(log log under mild assumptions on the distribution. More broadly, this line of research connects to earlier studies on compressed data structures with provable guarantees, such as the foundational work of Sadakane (2077
3 Methods
This section introduces our Learned Sort fremework and its PCF-basod instantiation. In Section 3.1 we set up the notation, in Section 3.2 we present the general framework, and in Soction 3.3 we instantiate with pas-b CDF model to obtain concrete complexity guarantees.
3

---

Published in Transactions on Machine Learning Research (10/2025)
X
56
50
CDF Model
Recursive model-base bucketing until |bucket|
t
CDF Model
(Piecewise Constant Function)
S9
2D
c
50
71
standard sort if bbcket]
2
0.5
standard sort if [buckkt]
60
E.()) Empirical CDF
21 22 23
24
24
26
F(g) Output of CDF model
Concatenate
X sorted
Figure PCF Learned Sort: First, the input array is partitioned into 7 + buckets using a CDF model- based method. Buckets larger than or smaller than т are sorted with a standard sort (e.g., IntroSort QuickSort). Otherwise, the recursive model-based bucketing is repeated. Finally, the sorted arrays are concatenated. The CDF model used for bucketing is Piecewise Constant Function (PCF). The function is constant within each interval, and the interval widths are constant.
3.1 Notation and Setup
Following the learned-sort paradigm Kraska et al. (2019); Kristo et al. (2020 2021a), our learned sort algorithm recursively applics model-based bucketing. Model- buckoting partitions the array into multiple buckets using CDF model trained on the input that the bucket with the larger ID gets the larger value.
Let D C IR be the domain of possible key values and D be the input array. For vector/arre write |v| for its length (number of clements), c.g., [ax] n. If |x] is smaller than fixed threshold E N, the algorithm falls back to classic sorting algorithm. We refer to this fallback classical sorting algorithm as the standard sort. As the standard sort, we can use any sorting algorithm, such as IntroSort, QuickSort, or the algorithm of Han (020).
we
For model-based bucketing, we define functions (n). 3(n), ((n).6(m) + N follows: (()) is the number of samples used to train the CDF model, ((n) is the number of PCF bins hyperparamcter; see Section 3.3 (()) + 1 is the number of buckets, and ō(n) is the threshold that determines the behavior after bucketing (see Section
3.2 For brevity, write a, 3, 6.6.
3.2 Learned-Sort Framework
Algorithm description. At a high level, our algorithm is a recursive model-basee bucketing scheme aug- mented with an exception-handling mechanism for bucketing "failures." This exception-handlin mechanism greatly simplifies the analysis of both expected and worst-case complexity. The overall workflow is visualized in Figure and the psendocode is given in Algorithm [
If the length of the input array is less than our algorithm sorts the input array using standard sort (c.g.. IntroSort or QuickSort). Otherwise, model-based bucketing is performed.
The model-based bucketing method M takes an input array x and partitions it into several buckets. First, all some elements of æ are used train the CDF model F: D - [o, 1]. The F(g) is trained to approximate (1....,m) n} 0 S gl/lz/. Any non-decreasing model can serve the CDF model F(g) (e-g., linear models, monotonic. ML.Ps, the PCF introduced in Section 3.3
the empirical CDF Fz (q)
4

---

Published in Transactions on Machine Learning Research (10/2025)
Algorithm The Learned Sort algorithin
Input: æ E I
Output: Fsorted IR (the sorted version x)
Subroutines:
STANDARD-SORH(()) : The standard sort with complexity guarantees (e.g, IntroSort QuickSort)
CDF-MODEL(Z) Instantiate a CDF Model F(g) that estimates Fx(q)
5: function LEARNED-SORT(C
6:
TI
- [
7: n < then
D. Small bucket
8:
return STANDARD-SORT(11)
F(g) - [], C2 1 11, ... Cy+1 f
CDF-MODEL((E)
Model-based bucketing
10:
11:
for = L.2...,n
12:
j j [((x))]] +1
13:
C..PPPEN((2)
14:
for ..2
Recursivcly sort and concatenate
15:
if ccl then
16:
Cj f STANDARD-SORT(C)
17:
clse
18:
Cj f LEARNED-SORT(c))
19:
Esorted f- CONCATENATEE(C, C2,
20:
return Fnrrted
After training, the CDF model used partition the input array æ into y buckets. All y + buckets, {e,)]=i> are initialized to be emply, and then for each E (I....,n), Ty is appended to c ([(e)))+1 This is based on the intuition that the number of elements less than equal to 2; in the array (i.e., Ii E (I, Øy S l) is approximately equal to nF((x.))
We restrict the CDF model F' to non-decreasing functions to ensure that the bucket with the larger ID gets the larger value, i... p E C2 A E Ck A j = p < This means that each bucket is responsible for a disjoint and continuous interval. Let ty = minsee; x (j = 1....., 1), ty+2 = oo, then the j-th bucket cj 11=1....,?? 1) responsíble for a continuous interval I₁ = (tz,))
After model-based bucketing, our algorithm determines for each bucket whether the bucketing "succeeds" "fails." For each j E ? + 1}, check whether the size of bucket C₁ is less than d. If c, > 8 (which mcans the bucketing "fails"), the bucket is sorted using the standard sort (c.g., IntroSort QuickSort). If leyl < (which means the bucketing "succeeds"), the bucket is sorted by recursively calling our Learned Sort algorithm. Note that the parameters such as y and 8 are redetermined for each recursion according to the size of the bucket (i.e., the input array the next recursion step), and the CDF model is retrained for each bucket. Finally, the sorted buckets are concatenated to form the sorted array.
Worst-case complexity. The following lemma guarantees the worst-casc complexity of our Learned Sort.
Lemma 3.1. Assume that there exisls a model-based bucketing algorithm M such that M can perform bucketing (including model training and inferences) an array of length into 1 O(n) buckets with a worst-case complexity of O()). Also, assume that the standard sort has a worst-case complexity of OnnU (n)), where (n) is non- con-decreasing function. Then, the worst- case complexity of our Learned Sort with such M and 5 = [ (where d is a constant solisfying 0 < <x 1) is On)((n) + n log log n).
This lemma can be intuitively shown from the following two points: (1) the maximum recursion depth is (log log and (2) each element the imput array æ undergoes several bucketing and only one standard sort. The first point can be shown from the fact that the size of the bucket in the i-th recursion depth is less than nd The second point evident from the algorithm's design since the buckets sorted by standard sort left. only to be concatenated. The exact proof is given in Appendix A.T
5

---

Published in Transactions on Machine Learning Research (10/2025)
Note that this guarantee critically relies the exception-handllng mechanism: without it, the recursion depth could reach (n)) and the worst-case time would degrade to (nn²), whereas with it the recursion depth is always bounded by O[log n).
Expected complexity. Next, we introduce a lemma about the expected computational complexity of our Learned Sort. The following assumption is necessary to guarantce the expected computational complexity. Assumption 3.2. The input array E "D" is formed by independent sampling according to probability density distribution f(x): D + Rzo.
Wc define fz(r): I + Ryo to be the conditional probability density distribution of f(x) under the condition that x I for interval I D ie., fz(x)= == Jr K(addy
((w)
The expected computational complexity of our proposed Learned Sort is guaranteed by the following lemma.
Lemma 3.3. Let xT. (E I") be the array formed by sampling nt times independently accorting to JT(x). Assume that there exist a model- based bucketing algorithm M and a constant d (E (0, 1)) that satisfy the following three conditions for any interval I (C D): (i) M can perform bucketing (including model training and inferences) on an array of length n, with an expected complexity of O(n), (ti) 7 + O(m),,,, and (tit)
Pe/ 2 In [n (112)) ( Also, assume that the standard sort has an expected complerity of (O logn). Then, the expected complexity of our Learned Sort with such M and 6 = [nn]] is On n).
This lemma can be proved intuitively by the following two points: (1) the maximum recursion depth is Oloo logn), n), and (2) the expected total computational complexity from the i-th to the (i + 1)-th recursion depth is (n). The first point is the same as in the explanation of the proof of Lemma 3.1 The second point holds because the expected computational complexity from the i-th to the (2 + 1)-th recursion depth is On logn) with probability O lagg), and (n)) in other cases. See Appendix A.2 for the exact proof.
Note that the assumption of Lemma 3.3 includes "M works well with high probability for any I (C D)." This is because our Learned Sort algorithm recursively repeats the model- based bucketing. The range of elements in the bucket, Le., the input array the next recursion step, can be any interval I D).
3.3 PCF Learned Sort
We now instantiate the framework with PCF Learned Sort, which satisfies the assumptions of Temma 3.1 and Lemma 3.3 thereby providing both worst-case and expocted-time guarantees. PCF Learned Sort ap- proximates the CDF using Piecewise Constant Funclion (PCF) with 8 equal-width bins; the model output is constant within each bin (see the right panel of Figure []. The study that develops Learned Index with a theoretical guarantec on its complexity (Zeighami & Shahabi 2023) also used PCF as a CDF model. While our framework admits more expressive CDF models (such as spline-based or neural models), we focus on PCF due to its minimal training and inference cost and the tractability of its theoretical analysis.
The model-based bucketing method in PCF Learned Sort MPCF trains the CDF model F as follows. The parameters a E (1....,m) n) and 8 E N are determined by n, where a is the number of samples used to train the model and B is the number of intervals in the PCF. The PCF is trained by counting the number of 2min)] + 1, where Tmin min, I; and Tmax = max; Fy. From x, a samples are taken to form a E D and i(z) is used to construct b z with b. = (j E (1, (1....,a) a i(az) S i)]- This counting procedure trains the PCF. Note that b is non-decreasing non-negative array and b341 = a, i.e., 0 < bi S b2 < b941
samples in each interval. We define i(x) = [(x 8/
Inference for F(x) is then given by F(x) = buts) Since i(œ) and are non-decreasing, F(x) is also non- decreasing, Also, 0 < F(x) < because 0 < b, < a for every i.
The following is a lemma to bound the probability that Mper will "fail" bucketing. This lemma is important to guarantee the expected computational complexity of PCF Learned Sort.
Lemma 3.4. Let 0n and 0g be respectively the lower and upper bounds of the probability density distribution (x) in D, and assume that O- < a S 02 xo. That is, D as f(x) S 02. Then, in model-based
6

---

Published in Transactions on Machine Learning Research (10/2025)
bucketing of xτ (E In) to {e, 1- using MPCF, the following holds for any interval I (C D):
76 2n
2027
a.K 27
1 1) 2
K
2 1 + Pr[Ej, leyl > 5] - exp
(1)
01
K
The proof of this lemma based on and combines proofs from two existing studies. The first is Lemma 5.2. from study of TPS'o (Axtmann et al.) 2022) efficient sample sort. This lemma guarantees the probability of "successful recursion step" when selecting pivots from samples and using them to perform a partition. This lemmn is for the method that does not use the CDF model, so the proof cannot be applied directly to our case, Another proof we refer to is the proof of Lemma 4.5. from a study that addressed the computational complexity guarantec of the Learned Index (Zeighami & Shahabi, 2023). This lemma provides a probabilistic guarantee for the error between the output of the PCF and the empirical CDF. Some modifications are required to adapt it to the context of sorting and to attribute it the probability of bucketing failure, i.e., Pr[ai, leyl 6]. By appropriately combining the proofs of these two lemmas, Lemma 3.4 is proved. The exact proof is given in Appendix A.3
Here, we emphasize that the assumption of this lemma, 0 < 01 S 02 < 0o, is sufficiently reasonable and "mild" as described in ZZighami & Shahabi, 2023). It asserts that the probability density function f(z) is both bounded and nonzero over its domain D. This class of distributions covers the majority of real-world scenarios because weal-world data is commonly derived from bounded and continuous phenomena, e.g., age, grades, and data over a period of time. Empirically, Zeeghamii & Shahabi (2023) further suggest that the ratio 02/01 lends to remain close to in wide variety of practical datasets, and even for more challenging cases like OSM, the ratio still appears to remain at most around 20.
Using Lemma 3.1 Lemma 3.3 and Lemma 3.4 we can prove the following theorems.
Theorem 3.5. If MPCF is the bucketing method, the worsl-case complexity of slandard sort is O(nU (n)) (where (n) is a non-decreasing function), and a = = = 5 = [n3//J, then the worst-case complexity of PCF Learned Sort is (n)((n) + log l).
Proof. When a= y |n3/4]] J, the computational complexity for model-based bucketing is O(n) because (i) the PCF is trained in Oaa + 3) = Onn34), and (ii) the total complexity of inference for n elements is On), since the inference is performed in O(1) per element. Therefore, since + = O()), the worst-case complexity of standard sort is (nnU(n)), and d = |n3/4,, we can prove the worst-case complexity of PCF Learned Sort is (nn((n)) + n nog logn) by Lemma 3.1
Theorem 3.6. Let on and 02 be the lower and upper bounds, respectively, of the probability density distri- bution fx) in D, and assume that < <i S 02 < co. Then, if MMpFF is the bucketing method, the expected complexity of standard sort is logn) and a = 3 = =?= = =n3//4, Learned Sort is O(n log logn). n).
then the expected complexity of PCF
Proof. When a B = 7 |/3/ the computational complexity for model- based bucketing is O()). Since |/] K for sufficiently large n, and
K D(Vn) when a 3 7
2n
aK
(1
1 }
exp
On' exp(- s O log
(2)
8
27
Given that 7 1 On), the expected complexity of standard sort is O(n log n), and = |n//4], it follows
from Lemma 3.3 and Lemma 3.4 that the expected complexity of PCF Learned Sort is O(n log log n).
Note that the exact value of ai and 02 is not required to run PCF Learned Sort since the parameters for this algorithm, ie., a, B, 7, and 8, are determined without any prior knowledge. In other words, PCF Learned Sort can sort in expected O(n log log n) complexity as long as < 01 S fxx) S 02 < co, even if it does not know the exact value of σ1 and 02- If 0₁ and 02 do not satisfy the assumption of Thoorem 3.6 the expected complexity of PCF Learned Sort increases to (nU(()) + n log log... Such scenarios arise, for

---

Published in Transactions on Machine Learning Research (10/2025)
instance, in heavy-tailed distributions, datasets with extremely sparse regions (01 0), cases where the density is highly concentrated at particular values (Ø2 = x)) However, thanks to the worst-case bound in Theorem 3.5 the complexity never exceeds (nn (m) + log log Thus, the algorithm remains robust even under distributions that do not fully satisfy the assumption.
Alternative CDF Models. Our framework is not limited to PCF; it can also accommodate more expres- sive CDF models. For instance, we can replace PCF with spline-based model that approximates the CDF by interpolating the empirical distribution at bin boundaries. Concretely, given /3 intervals, we evaluate the empirical CDF at the endpoints of each interval and then construct a piecewise linear spline that connects these values, yielding a continuous and non-decreasing CDF approximation. We refer to the algorithm that applies this apline-based CDF model within our Learned Sort framework as Spline Learned Sort. We show that spline-based models constructed in this way st.ill satisfy the assumptions of Lemma 3.3 and thus the expected time complexity guarantee of O(n log n) remains valid. A detailed theoretical proof for the spline-basen case is provided in Appendix A.5
4 Experiments
In this section, we empirically validate our theoretical results. First, in Section 4.1 we confirm that the complexity of PCF Learned Sort is O(n log logn) n) for both synthetic and real datasets. Then, in Section 4.2 conduct experiments with various parameter settings and empirically confirm Lemma 3.4 a lemma that bounds the probability of bucketing failure and plays a crucial role in guaranteeing the expected complexity of PCF Learned Sort. Finally, in Section 4.3 we present from sorting time measurements.
Setup. We experimented with synthetic datasets created from the following four distributions: uniform (min = 0, max = 1), normal (u= 0, 1), exponential (A = 1), lognormal (u 0, = 1). The input array generated by independently laking samples from each distribution. Only the uniform distribution satisfies the theoretical assumptions required for our complexity guarantees. The other distributions violate these assumptions, but we include them to evaluate the empirical robustness of PCF Learned Sort.
We also used the following 16 real datasets, including Chicago [Start, Tot] CCicagoo 2021 : NYC
[Pickup, Dist, Tot] (uyel 2020), SOF [Humidity, Pressure, Temperature] (avvrdieev 2019 Wiki, OSM, Books, Face (Marcus et al. 2020), and Stocks [Volume, Open, Date, Low] (Onyshchak 2020 Further dataset details are provided in Appendix B For each dataset, randomly sample elements, shuffle them, and use them as an input array to examine the complexity of the sort algorithms. Since these are real-world datasets, we cannot definitively determine whether they satisfy our theoretical assumptions. However, as shown in the histograms in Figure Chicago [Start], NYC [Pickup, Tot], SOF [Humidity]] and Face appear to distribute values across a relatively dense and continuous domain, aligning well with our as- sumptions. In contrast, other datascts exhibit long tails or sparse regions, suggesting that our assumptions may not hold. Furthermore, note that for several datasets (Chicago [Start, Tot], NYC [Dist, Tot), SOF [Humidity, Pressure, Temperature], and Stocks [Volume, Open, Date, Low]), the number of unique values is extremely small (less than 3.2% of the total elements, as detailed in Appendix Bh.
All experiments were run on a Linux machine equipped with an Intel CMre i9-1 19-11900H CPU @ 2.50GHz and 62GB of memory. GCC version 9.4.0 was used for compilation, employing the -03 optimization flag.
4.1 Computational Complexity of PCF Learned Sort
We meticulously counted the total number of basic operations for sorting the input array to observe the computational complexity of each sorting algorithm. Here, the basic operations consist of four arithmetic operations, powers, comparisons, logical operations, assignments, and memory access. We chose this metric, which counts basic operations, to mitigate the environmental dependencics observed in other metrics, such as CPU instructions and CPU time, which are heavily influenced by compiler optimizations and the underlying hardware. This is the same idea the metric selection in the experiment of (Zeighami & Shahabi 2023).
8

---

Published in Transactions on Machine Learning Research (10/2025)
Uniform
Norma
Expomentia
Lognormal
Chicago [Statt
Chicago TTtt
#Operattors fe
#Operations 1
#Opersoors
Denslty #Operatiors
#Oporotiors
120
Dersiyy
Deratyy
Dersty
Value NYC (Pickou)
Value NYC (Dist
Value NYC (Tbt]
Value SOF (Humidity
Value SOF (Prsssure)
SOF Tempeertuure]
Dersity #Operations E 5
#Operations in
@Operationss i
#Operetions
8 2 2 :
#Operetiers
#Opera
Dersly
Duriity
Value Wild
Value OSM
Velue
Value Pace
Value
Beakss
#Operatiors n.
#Operations in
#Operations
Dengtyy
Denetyy
Deralty
PCF Learned Sort (Proposed)
Spline Learned Sort (Proposed)
Value Stocks [Volume]
Value
Value
Value Stecks Low
-
Quick Sort
#Operattors n.
Stocks [Open]
Stocks (Daee]
Radix Sort
#Operations
g
#Opersooond
Learned Sort (Kristo al., 2021)
Denaly
sit
Value
Value
Vilue
Figure 2: Number of operations to sort the array. Below each graph is histogram visualizing the distribution of each dataset. The standard deviation of the 10 measurements represented by the shaded area. Our PCF Learned Sort consistently achieves complexity lower than O(n log while Learned Sort 2.0 (Kristo et al. 2021a), which has O(e)) worst-case complexity, occasionally requires huge operations.
= 7 [n3/4| and = 100. As the standard sort, we used QuickSort, which has an expected complexity of O(n log n). For ease of implementation and straightforward measurement of comparison counts, we chose QuickSort. We compared our PCF Learned Sort against (plain) QuickSort, radix sort, and Learned Sort 2.0 (Kristo et al. 2021b). Learned Sort was selected as the learned-method baseline because allows relatively simple counting of operations (a broader comparison appcars in the sorting time experiments of Soction
The parameters of PCF Learned Sort set in Theorems 3.5 and 3.6
Figure 2 shows the number of operations divided by the length of the input array, Each point represents 10 runs, with the shaded region indicating the standard deviation. Note that the horizontal axis is logarithmic. As a result, the curve for QuickSort (with O(n log n) complexity) appears approximately linear in this plot for synthetic dat asets and real-world datasets with few duplicates (i.e., NYC [Pickup), Wiki, OSM, Books, and Face). In contrast, the curve for PCF Learned Sort is nearly flat, suggesting a complexity significantly lower than On log PCF Learned Sort consistently requires the fewest operations across all conditions, achieving up 2.8 times fewer operations than QuickSort. These results confirm not only our theoretical analysis but also the robustness of PCF Learned Sort under assumption-violatin scenarios.
the average

---

Published in Transactions on Machine Learning Research (10/2025)
0.75,d = 0.75
0.75, = 0.75
h 0,75, = 0.75
0.75, d 0.75
0.75, 0.75
0.75, b
0.75
a
a
a
8. The variables a, b, c, d, except those on the x- and y-axes, were set to 0.75. The white dotted line represents the parameters that make the right side of Equation ① equal to 0.5. The close alignment between this white dotted line and the actual success /fail boundery suggests the theoretical bound by is Equation reasonably tight.
Figure 3: Healmap showing the empirical frequency of bucketing failure, i.e, 3j, Jj
For datasets with many duplicates, QuickSort, Learned Sort 2.0 (Kristo al. 2021a), and PCF Learned Sort all exhibit relatively few operations. This bchavior arises bocause highly duplicated datasets often result in buckets containing only one distinct value, allowing the algorithms to terminate early. Even under such conditions, PCF Learned Sort performs fewer operations than the other algorithms.
The curve for radix sort also flat but lies consistently above that of PCF Learned Sort. This due to the difference in partitioning strategies. While the radix sort partitions at a fixed gramularity, our PCF Learned Sort performs partitioning using intervals that are adaptively set by the learning model.
In particular, on the SOF [Temperature] dataset with medium input sizes (2 10 < 2 107), Learned Sort 2.0 incurs extremely high costs: while all other methods keep the number of operations per below 100, it can exceed 50,000. This shows that Learned Sort methods without worst-case guarantees may suffer from pathological overhead. By contrast, our method maintains both expected and worst-case guarantees, ensuring robust performance across diverse datasets.
4.2 Confirmation of Lemma 3.4
Lemma 3.4 bounds the probability that bucket of size greater than d exists. This is an important lemma that allows us to guarantee the expected computational complexity of PCF Learned Sort. Here, we empirically confirm that this upper bound is appropriate.
We have experimented with a 1, B = 0.05 intervals. For each a, b, c, d setting, the following was repeated 100 times: we took n 10 elements from the uniform distribution to form the input array and divided the array into + 1 buckets by MMCFF, and chocked whether or not 3j, lcyl > Thus, for each a, b, c, E (0.05, 0.10...., 0.955,, we obtained the empirical frequency which bucketing "fails."
[nd], varying a, b, c, d from 0.05 to 0.95 at
Heat maps in Figure show the empirical frequency of bucketing failures when two of the b, c, d parameters are fixed, and the other two parameters are varied. The values of the two fixed variables are set to 0.75, e.g., in the upper left heap map of Figure 3 (horizontal axis is and vertical axis is b), c == d = 0.75. The white dotted line represents the parameter so that the right side of Equation ①1 is 0.5. That is, Lemma 3.4 asserts that "in the region upper right of the white dotted line, the probability of bucketing failure less than 0.5."
We observe that the white dotted line close to (or slightly to the upper right of) the actual bound of whether bucketing "succeeds" or "fails" more often. This suggests that the theoretical upper bound from Lemma 3.4 agrees well (to some extent) with the actual probability. We can also confirm that, as Lemma 3.4 claims, the probability of bucketing failure is indeed small in the region upper right of the white line.
4.3 Experiments on Sorting Time
We empirically compare the sorting time of our PCF Learned Sort against several baselines. Note that the metric used in Scction [4.]] the number of operations, does not change depending on the machine or compilation method, but the sorting time does. As the standard sort used in PCF Learned Sort, we used std:: which has worst-case complexity of O(nlogn). We compared our PCF Learned Sort with
10

---

Published in Transactions on Machine Learning Research (10/2025)
14-
Uniform
1.2
Normal
Exponential
Lognormal
16
Chicago [Star SSartt
Chicago (Tot)
Timu (5)
Thme Es
TIme
NYC [Pickup]]
NYC [Dist]
NYC ITx
S0F [Humidiv]
SOF (Pressune]
SDF [Temperauure
Time Islrn
Time 1:
T 441
lime
Wikd
OSM
Books
Face
Time 1
Lime [5]
Time Is]in
PCF Learned Sort (Proposed)
Spline Learned Sort (Proposed)
std::sort
Radix Sort
buss::sotttssrraadottttttttttt
154o (Axtmann et al., 2017|
Stocks [Votume]
Stockss Open]
Stocks [Date]
(Low)
Leamed Sort 2.0 (Kristo et al., 2021)
Timea [S] In
BLS (Ferragina et al., 2025)
Tima [S)
Time 6
ULS (Ferragina et al., 2025)
Learned Sort 2.1 (ferragina et al., 2025)
12
Figure 4: Time to sort the array. The standard deviation of the measurements represented by the shaded area. Our PCF Learned Sort is significantly faster than std: sort, and more importantly, it maintains robust performance across all datasets, whereas other learned sorts without worst-case guarantees can suffer catastrophic slowdowns, as seen with Learned Sort 2.0 on the SOF [Temperaturo] dataset.
std:: :sort radix sort, boost: sort:: :spreadsorts :float sort (Boost C++ implementation of Spread- sort (Ross) 2002)), and Learned Sort 2.0 (Kissto et al.) 2021b). In addition, we evaluated more recent
state-of-the-art learned sorting algorithms Ferragina & Odorisio
2025 -Balanced Learned Sort (BLS),
Unbalanced Learned Sort (ULS), and Learned Sort 2.1 as well IS4o
(Axtmann et al. 2017). one of the
state-of-the-art non-learned sequential sample sort algorithms.
Figure shows the sorting time divided by n. It shows the mean and standard deviation the 10 mea- surements for each condition. Note that the horizontal axis is logarithmic, and therefore the curve of std: :orrt, which has a complexity of O(n logn,, is almost linear this plot for synthetic datasets and real-world datasets with few duplicates. In contrast, our PCF Learned Sort graph shows relatively slow increase, suggesting that PCF Learned Sort has a complexity much smaller than log n). We see that PCF Learned Sort is up to 2.5 times faster than std: sort. Furthermore, we find that for relatively large n (> 10%), our PCF Learned Sort usually outperforms not only radix sort but also Spreadsort, an algorithm that cleverly incorporates the advantage of comparison sort into radix sort.
The figure also shows that highly optimized methods like IS4o and other learned sorts often outperform PCF Learned Sort in average speed. This is bocause these methods are highly optimized implementations that consider factors like cache efficiency, whereas our implementation prioritizes providing rigorous theoretical guarantees. However, this speed comes at the cost of robustness: learned sorts without worst-case guarantees can suffer catastrophic slowdowns. For example, on the SOF [Temperature] dataset with = 2 Learned Sort 2.0 took up to 326.4 4 seconds, while our method consistently finished in 0.45 seconds. Moreover, as shown in our adversarial analysis (Appendix() Ch, other recent. learned sorts (BLS, ULS, Learned Sort 2.1) also exhibit vulnerabilities. These results highlight the practical value our theoretical guarantees.
To better understand runtime behavior, we profiled PCF Learned Sort across its stages (Appendix DJ. The results show that while the training stage is consistently lightweight across datasets and input sizes, the
11

---

Published in Transactions on Machine Learning Research (10/2025)
bucketing stage often becomes the bottleneck. The dominant cost varies depending on both and the dataset characteristics, suggesting opportunities for further optimization.
5 Discussion
Comparison with (Zeighami & Shahabi, 2024). Most recently, a concurrent work (Zeighami & Sha- habil 2024)) introduced a theoretical framework for learned database operations, including sorting, indexing, and cardinality estimation. key strength of their approach is the formal definition of "distribution learnabil- ity" and its applicability to a broad class of distributions, including those subject to distribution shifts. Using this framework, they developed Learned Sort algorithm with an expected running time of O(n log log n) under certain distributional assumptions. While their approach employs a bucketing-base based sorting algorithm similar to ours, there are several key differences between their method and ours.
First, their algorithm relies on detailed prior knowledge about the distribution; it explicitly requires a parameter X2, which represents the "learning possibility" of the distribution (see Definition 3.2 in (Zeighami & Shahabi 2024) for details). Since x2 depends on Pi and p2, their algorithm cannot be executed without knowing the values of Pı and P2 (or at least their lower and upper bounds). In contrast, our algorithm does not require these values, making more widely applicable.
Second, they do not provide experimental results. Since estimating Pr and P2 from real data is challenging, empirical evaluation of their method is difficult. On the other hand, since our algorithm does not depend on these specific values, it is easy to implement and evaluate experimentally.
Finally, their algorithm lacks a worst-case complexity guarantee. In particular, there are cases where the algorithm may not terminate, making it impossible to give an upper bound on its worst-case complexity. In contrast, we provide formal worst-case complexity guarantee.
Limitations of the Current Theoretical Framework. Our proof of the O(n log log expected com- plexity (Theorem 3.6), does not extend to distributions with f(z) = 0 or oc. similar limitation is observed in Learned Indexes (Zeighami Shahabi 2023), and extending the theory to cover a broader class of dis- tributions remains an open direction in both Learned Indexes and Learned Sorts contexts. One promising direction is to integrate more advanced CDF approximation methods with theoretical guarantees into our Learned Sort algorithm. By adopting refined CDF model and bucketing algorithm that satisfies the conditions of Lemma 3.3 it may be possible to achieve stronger theoretical guarantees.
Implementation Considerations and Optimizations. A straightforward implementation of PCF Learned Sort is not in-place, as it requires an auxiliary buffer for buckets nearly as large as the input. Engineering techniques from highly optimized sample-sorl implementations (Axtmann et al.) 2017 2022) suggest in-place variants without changing the asymptotic structure of our algorithm. Another important aspect is real-world efficiency: optimizing memory access patterns to enhance cache efficiency, reducing cache misses, and leveraging cache-aware data layouts could improve empirical performance without compromising theoretical guarantees. Dynamically tuning parameters such as a, B, 7, and based on the input distribution may yield further performance gains while maintaining guarantees.
Parallelization Potential. Although our analysis targets the sequential setting, the structure of PCF Learned Sort admits parallclization at several stages: training the CDF model, computing bucket IDs, scat- tering into buckets, and sorting buckets are all amenable to data parallelism. This observation is consistent with prior engineering work that integrates learned partitioning with high-performance (in in-place) sample-
sort pipclines and parallel learned-sorting frameworks (Axtmann al. 2017 Carvalho 2022 Carvalho &
Lawrence 2023). These results complement our thcoretical analysis and suggest opportunities for developing parallel learned-sorting algorithms with provable guarantees.
12

---

Published in Transactions on Machine Learning Research (10/2025)
6 Conclusion
We proposed PCF Learned Sort, which provides guarantees on both its expected and worst-case complexities. We then confirmed these computational complexities empirically on both synthetic and real data. This is the first study to support the empirical success of Learned Sort theoretically and provides insight into why Learned Sort is fast.
13

---

Published in Transactions on Machine Learning Research (10/2025)
References
Tle trip record data, 2020. URL http://ppww/ht//...////////////a
page
Antonios Antoniadis, Christian Coester, Marek Fliáš, Adam Polak, and Bertrand Simon. Online metric algorithms with untrusted predictions. ACM Transactions Algorithms, 2023.
Michael Axtmann, Sascha Witt, Daniel Ferizovic, and Peter Sanders. In-Place Parallel Super Scalar Sam- plesort (TPSSSSo). In 25th Annual European Symposium on Algorithms (ESA 2017), volume 87 of Leidniz International Proceedings in Informatics (LIPIcs), pp. 9:1-9:14. Schloss Dagstuhl-Leiin Heastuhl-Leibniz-Zentrrm fuer Informatik, 2017. doi: 10.4230/T.I S000//IPTss..SA.. 201.0...
Michael Axtmann, Sascha Witt, Daniel Ferizovic, and Peter Sanders. Engineering in-place (shared-memory)) sorting algorithms. ACM Transactions Parallel Computing, 2022.
Xingjian Bai and Christian Coester. Sorting with predictions. Advances in Neural Information Processing Systems, 2023.
Ivan Carvalho. Towards parallel learned sorting. ar preprint urXiv:2208.0000 06900, 2022.
Ivan Carvalho and Ramon Lawrence. Learnedsort as a beamning-augmented samplesort: Analysis and par- allelization. In Proceedings of the 35th International Conference on Scientific and Statistical Database Management, pp. 1-9, 2023.
T.-H. Hubert. Chan, Enze Sun, and Bo Wang. Generalized sorting with predictions revisited. In Frontiers of Algorithmics, 2023.
City of Chicago. Taxi trips: City of chicago: Data portal, May 2021. URL -meuu
org
Michael Dinitz, Sungjin Im, Thomas Lavastida, Benjamin Moseley, and Sergei Vassilvitskii. Faster matchings via learned duals. Advances in Neural Information Processing Systems, 2021.
Thomas Erlebach, Murilo de Lima, Nicole Megow, and Jens Schlöter. Sorting and hypergraph orientation under uncertainty with predictions. In Proceedings of the International Joint Conference Artificial Intelligence (IJCAI), 2023.
Paolo Ferragina and Mattia Odorisio. Fast, robust, and learned distribution-base sorting. IEEE Access, 13:45198 1415119---421,,, 2025.
Paolo Ferragina and Giorgio Vinciguerra. The pgm-index: a fully-dynamic compressed learned index with provable worst-case bounds. Proceedings of the Very Large Data Bases Endowment, 2020.
Paolo Ferragina, Filippo Lari, al. Fl-rmq: A learned approach to range minimum querics. LEIBNIZ INTERNATIONAL PROCEEDINGS IN INFORMATICS, 331:1-23 23, 2025.
Donald Frazer and Archie C McKellar. Samplesort: A sampling approach to minimal storage tree sorting. Journal of the Association for Computing Machinery, 1970.
Sreenivas Gollapudi and Debmalya Panigrahi. Online algorithms for rent-or-buy with expert advice. Proceedings of the International Conference on Machine Learning, 2019.
Yijie Han. Deterministic sorting in o(n log log n) time and linear space. In Proceedings of the Annual ACM Symposium on Theory of Computing, 2002.
Yijie Han. Sorting real numbers in o(n slrt(log n)) time and linear space. Algorithmica, 2020.
Yijie Han and Mikkel Thorup. Integer sorting in o(n sqrt(log log n)) expected time and linear space. In Proceedings of the Symposéum on Foundations of Computer Science, 2002.
Sungjin Im, Ravi Kumar, Aditya Petety, and Manish Purohit. Parsimonious Maaming--ugmment caching. In Proceedings of the International Conference Machine Learning, 2022.
14

---

Published in Transactions on Machine Learning Research (10/2025)
Java. List (java 21 & jck 21). URL: https://docs oracle. cotp:////aaaaaaaaaaaaaa/////////
base/ jassejavv/utaae jawa/ttii/isst. html (java. www.tttiii...... Comparator) 2023. Accessed on 2024-01-18.
Andreas Kipf, Ryan Marcus, Alexander van Remen, Mihail Stoian, Alfons Kemper, Tim Kraska, and Thomas Neumann. Radixspline: a single-pass learned index. In Proceedings of the international workshop on exploiting artificial intelligence techniques for data management, 2020.
Tim Kraska, Alex Beutel, Ed H. Chi, Jeffrey Dean, and Neoklis Polyzotis. The case for learned index structures. In Proceedings of the International Conference on Management. of Dala, 2018.
Tim Kraska, Mohammad Alizadeh, Alex Beutel, Ed H Chi, Jialin Ding, Ani Kristo, Guillaume Leclere, Samuel Madden, Hongzi Mao, and Vikram Nathan. Sagedb; learned database system. In Proceedings of the Conference on Innovative Data Systems Research, 2019.
Ani Kristo, Kapil Vaidya, Ugur Çetintemel, Sanchit Misra, and Tim Kraska. The case for learned sorting algorithm. In Proceedings of the ACM SIGMOD International Conference Management of Data, 2020.
Ani Kristo, Kapil Vaidya, and Tim Kraska. Defeating duplicates: A re-design of the learnedsort algorithm.
arXiv preprint arXix:2007.0550 03290, 2021a.
Ani Kristo, Kapil Vaidya, and Tim Kraska. LearnedSort, License: GPL 3.0. URL: https://github. com/ anlaristoo/eaarnedSott 2021b. Accessed on 2024-01-18.
Alexandra Anna Lassota, Alexander Lindermayr, Nicole Megow, and Jens Schlöter. Mininalistic predictions to schedule jobs with online precedence constraints. In Proceedings of the International Conference on Machine Learning, 2023.
Silvio Lattanzi, Thomas Lavastida, Benjamin Mosoley, and Sergei Vassilvitskii. Online schoduling via learned weights. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithmss, 2020.
Yujia Li, Felix Gimeno, Pushmeet Kohli, and Oriol Vinyals. Strong generalization and efficiency in neural programs. arXiv preprint ar arXiv:2007.03629, 2020.
Pinyan Lu, Xuandi Ren, Enze Sun, and Yubo Zhang. Generalized sorting with predictions. In Symposium on Simplicity in Algorithms (SOSA), 2021.
Thodoris Lykouris and Sergei Vassilvitskii. Competitive caching with machine learned advice. Journal of the Association for Compuling Machinery, 2021.
Ryan Marcus, Andreas Kipf, Alexander van Renen, Mihail Stoian, Sanchit Misra, Alfons Kemper, Thomas Neumann, and Tim Kraska. Benchmarking learned indexes. Proceedings of the Very Large Data Bases Endowment, 2020. Accessed on 2024-01-18.
Hristo Mavrodiev. Sofia air quality dataset, Sep 2019. URL quulaairrruullttyytttttt
Peter Mcllroy. Optimistic sorting and information theoretic complexity. In Proceedings of the ACM-SIAM Symposium on Discrele algorithms,, 1993.
Michael Mitzenmacher. A model for learned bloom filters and optimizing by sandwiching. Advances in Newral Information Processing Systems, 2018.
Michael Mitzenmacher and Sergei Vassilvitskii. Algorithms with predictions. Communications of the ACM, 2022.
Ian Munro and Sebastian Wild. Nearly-optimal mergesorts: Fast, practical sorting methods that optimally adapt to existing runs. In Furopenn Symposium on Algorithms, 2018.
David R Musser. Introspective sorting and selection algorithms. Software: Practice and Experience, 1997.
15

---

Published in Transactions on Machine Learning Research (10/2025)
Arvind Narayanan, Saurabh Verma, Eman Ramadan, Pariya Babaie, and Zhi-Li Zhang. Deepcache: A deep learning based framework for content caching. In Proceedings of the Workshop on Nelwork Meets AT & ML, 2018.
Omar Obeya, Endrias Kahssay, Edward Fan, and Julian Shun. Theoretically-effcient and practical par- allel in-place radix sorting. In Proceedings of the ACM Symposium Parallelism in Algorithms and Archileclures, 2019.
Olch Onyshchak. Stock market datasct, Apr 2020.
URL bttps://ww..agggll..cooooceoooo
stock-markett-ataase
Tim Peters. Python: list.sort. URL: http://ggw...t........//////////
listsort. txt, 2002. Accessed on 2024-01-18.
Manish Purohit, Zoya. Svitkina, and Ravi Kumar. Improving online algorithms via ml predictions. Aduances in Neural Information Processing Systems, 2018.
Dhruv Rohatgi. Near-optimal bounds for online caching with machine learned advice. In Proceedings of the ACM-SIAM Symposium Discrete Algorithms, 2020.
Steven J Ross. The spreadsort high-performante general-case sorting algorithm. In PDPTA, 2002.
Kunihiko Sadakane. Compressed suffix trees with full functionality, Theory of Computing Systems, 41(4): 589-607, 2007.
Shinsaku Sakaue and Taihei Oki. Discrete--onvex--aallliss based framework for warm-starting algorithms with predictions. Advances in Neural Information Processing Systems, 2022.
Atsuki Sato and Yusuke Matsui. Fast partitioned learned bloom filter. Advances in Neural Information Processing Systems, 2023.
Atsuki Sato and Yusuke Matsui. Fast construction of partitioned learned bloom filter with theoretical guarantees. arXiv preprint 1xXi:2410.13275 2024.
Yongho Shin, Changyeol Lee, Gukryeol Lee, and Hyung-Chan An. Improved aarmineg-uugmetedd algorithms for the multi-option ski rental problem via best-possible competitive analysis. In Proceedings of the Inter- national Conference on Machine Learning, 2023.
Kapil Vaidya, Eric Knorr, Tim Kraska, and Michael Mitzenmacher. Partitioned learned bloom filter. In International Conference on Learning Representations, 2021.
Youyun Wang, Chuzhe Tang, Zhaoguo Wang, and Haibo Chen. Sindex: a scalable learned index for string keys. In Proceedings of the ACM SIGOPS Asia-Pacific Workshop on Systems, 2020.
Sepanta Zeighami and Cyrus Shahabi. On distribution dependent sub-logarithmic query time of learned indexing. In Proceedings of the International Conference on Machine Learning, 2023.
Sepanta Zeighami and Cyrus Shahabi. Theoretical analysis of learned database operations under distribution shift through distribution learnability. In Proceedings of the st International Conference on Machine Learning, 2024.
16

---

Published in Transactions on Machine Learning Research (10/2025)
A Proofs
Here, we give the proofs omitted in the main paper. In Appendix A.1 we give the proof of Lemma 3.1 which is important for proving the worst-case complexity of PCF Learned Sort. Appendix A.2 and Ap- pendix A.3 give proofs of Lemmn 3.3 and Lemma 3.4 respectively, which are important for proving the expected computational complexity of PCF Learned Sort. The quantization-aware version of Lemma 3.4 and Theorem 3.6 defined and the proof is given in the Appendix A.4 Finally, provide the proofs of the theorems guaranteeing the complexity of Spline Learned Sort in Appendix A.5
A.1 Proof of Lemma
Proof. Let P(n) be the worst-case complexity of our Learned Sort when using the model-based bucketing algorithm M as assumed in Lemma 3.1 and 8 = In*]. Let S(n) be the worst-case complexity of the standard sort and R(n) be the worst-case complexity of model-based bucketing (including model training and inferences). Since S(n) = OnU (n)) and the standard sort terminates after a finite number of operations,
C1,4 (> 0), n nz0 0 + S(n) S C1 + LnU(()).
(3)
Since R(n) (n) and y + 1= +n)=
3 n2, l2 (> 0), n
R(n)= S 12n.
(4)
3 n3, la (> 0), n n2 7 7+1 < lzn.
(5)
In the following, we prove P(n) OnU nog logn) by mathematical induction.
First, for n max R3, T) =: no, there exists constant C (> 0) such that P(n) I C. That is, for no: our Learned Sort terminates in finite number of operations. This is because, since 6 < n, the bucket will either be smaller than the original array length or the bucket will be immediately sorted by the standard sort.
Next, assume that there exists a constant C' (> 0) and ( (> 0) such that P(n) S C + ((nli (n) + n log for all < k, where an integer such that 2 no. Without loss of generality, we assume that 2 C and 41 Let Sy,k be the set consisting of all (1 + 1)-dimensional vectors of positive integers whose sum is k, i.e., Sy,h = EZo E 8; k.. Then,
++
P(k) S R(k) + max
Σ
[1ss 2 [.]]]- S(x,) 118, < [A]]] P(s.)
aES,.
++1 Σ
< 12k + max sES,,
[1[s 2 1a [ + (1,,U(ssss))) + 1[s < [b (C + +s(UU((ss) + s, s;))
(6)
1kk + max BES.,k
+ C+lsUU(ss)) + 1s log log ):a)
122 + C(7 + 1) + (k) + 1k log log kad
$ 12k + Clyk IkU (k) + lk log log 1k log
1 Cla - -llog 2) k: + (C (k) + A log log k)).
Therefore, if we take such that
12 + Cls
log 21,
(7)
then P(k) < C + ((KU(k) + k log log k) (note that the left side of Equation 7 is a constant. independent of k).
Hence, by mathematical induction, is proved that there exists a constant C (> 0) and (> 0) such that P(n) & C (kk 1k log log k) for all N.
17

---

Published in Transactions on Machine Learning Research (10/2025)
A.2 Proof of Lemma 3,3
Proof. The proof approach is the same as in Lemma 3.1 but in Lemma 3.3 the "expected" compulational complexity is bounded. The following two randomnesses are considered for computing the "expected" com- putational complexity: (i) the randomness with which n elements are independently sampled according to the probability density function f(z) in the process of forming the input array æ, and (ii) the randomness of the PCF Learned Sort algorithm sampling a elements from the input array x for training the PCF.
Let T(a) be the expected complexity of our Learned Sort when using the model-based bucketing algorithm M as assumed in Lemma 3.3 and 5 = |nd]. Let S(n) be the expected complexity of the standard sort and R(n) be the expected complexity of model-based bucketing (including model training and inferences). Since
((n) = (n logn) and the standard sort terminates after a finite number of operations,
3 C1,4 (> 0), n n20 = S(n) S Ci + linlogn.
(8)
Since R(n) (m)) Pr[Fij |cyl 2 In (11 (1//og n)), and 7 1 O(n),
n2 l2 (> 0), n 2 n2 = R(n) S 12n,
(9)
L3 log n
n3, 13 (> 0), n 2 na
Prßj. | 2 |n -
(10)
344,4 (> 0), 2 n44 + 7+15 S 4n
(11)
In the following, we prove T(n) O(n loggnn) by mathematical induction.
First, for n < max(ng, n3, 7) =: no: there exists a constant C (> 0) such that T(n) S C. That is, for n < no: our Learned Sort terminates in a finite number of operations.
Next, assume that there exists a constant C (> 0) and / (> 0) such that T(n) S C. In log for all n < k where h is an integer such that 2 no. Then, from & 2 m2,
+1
т(k) S R(k) + E
A|le
2 [4_ S(c,)) Alle,/
[44]] T(le,))
< 12k + Pr [e [=-]] E
s(le))) +E Σ 1 1/c [1-]] T(le))
(12)
++1
S 12k Pr cell 2 [A_]] (Ci((C + hhg
Σ (Imin(11)),1s))
Here, from 2 ng and 2 n4:
Pr 2 [K4]] 1) < 13
(Ci44 + lk
logk
(13)
$ (Cilsl4 + klzsk.
Also, from the assumption of induction and k 2 n4.
E
T [
|,1g)1
< E
{c 1- min([ 1, lc,l)) log log min (1x*),
x+
< E
1- C(1 - 1)+ + Σ
1c,e log log J
(14)
1=1
< Cl4k + 1k log log [
< Club + 1k log d + 1h log log k.
18

---

Published in Transactions on Machine Learning Research (10/2025)
Therefore,
T(k) 2 12k + 1614444440 + Clab + 11: log d + 1k log log k
s s 1/ + C4 llo 7
1
(15)
k (C + 1k log log k).
Therefore, if we take such that
l2 + C1lal1 + 4113 l + Cl4
1
(16)
log
then T(k) S + lee log log k (note that the left side of Equation 16 constant independent of ks).
Hence, by hemaaiil induction, is proved that there exists a constant C (> 0) and (> 0) such that [mn) SC In log log for all N.
]
A.3 Proof of Lemma 3.4
We first present the following lemma to prove Lemma 3.4
Lemma A.1. Let e (E In) be a sorted version of æy (E Ia) and Tmax are the minimum and marimamm values of vI, respeclively).
(xmax Tmin)/3 (where Tmin and
Also, define the set S, and Tr follows (r I.)..,
S. = (k] [ + < ck Se, D}, T= (k er Ase ek <min(r+6/22))) A}.
(17)
Using this definition, define Yjr; Zero Yr, Zr as follows (j = ,,
a, r (JET.) (else)
n..
Fr {1
( (else)
25r 3 {1
a Y, Σ
im
Z,
Zir
(18)
==1
When using MPCF, if the size of the bucket to which e, is allocated is greater than or equal to o, the following holds:
+1 Y, < : v rrsn A Z, < - 1
(19)
Proof. We prove the contraposition of the lemma. That is, we prove that e, is allocated to a bucket smaller than d under the assumption that (r< + V Y, [ (r>n- v Z, a
For convenience, we hypothetically define eo enc oc, and assign ep the Oth bucket and ex+1 to the (7 + 2) bucket. The size of the Oth bucket and the (7 2)-th bucket are both 1.
First, we prove that e, and 1)1 are assigned to different buckets. When n- n-8/2 <r n, and (min()446/2n++1) = Cn+1 are obviously assigned to different buckets. When r S n 6/2, the ID of the bucket to which e, is assigned is
[f()) +1
7
+1
a
7 bi(e)) +1
0
(20)
7
Kí i(a,) S i((e)) +1
a
?
Ki a, (
+ + +1
a
19

---

Published in Transactions on Machine Learning Research (10/2025)
The ID of the bucket to which 6min(r+6/22m++1) cr+0/2 is assigned is
[ +1 be(e) + 1
2 a
bi(or45/2)
(21)
| | i(aa) S ((cr+6/2))
|i I a3 S Er+6/2
Thus, taking the difference between these two bucket 1Ds,
(LF(er48/2)1) +) - (LF(e)))]+))
> 2 {i aj e - A}} - (2 | as s +
7 || e, + A < a e - A} -1
[Tll -1
(22)
1
Σ
Zjr
j=1
a
Therefore, ey and (1in((+662,m+1) are assigned to different buckets.
In the same way, we can prove that (max(0,r-6/2)) and e, also assigned to different buckets. Thus, the size of the bucket to which is assigned is at most 8 - (at most from 6msx(0,r-622++1 to (min(++6/2.n+1)-1 and the contraposition of the lemma is proved.
Using Lemma A.1 we can prove Lemma 3.4
Proof. Let q max f A fz(z)dz (where y is value such that (v, y + A) IJ. Then, from 01 $ f(x) 02 for all x E I,
maxy S 1y flyddy
q S
f(x)d
max, f o2dy
12 oida
(23)
A2A
01 (Fmax Mmin))
02
BB
Thus, when r >
2 + 1,
5
E
8
|8,1
F.
[8
[[k
6,- A <e S er - |]]-
2
2
IE [[(k]
6--6/2 < 6k < 6/- + |} + EE [H 6, -c- e
(24)
< nb ng
202n
o 3
20

---

Published in Transactions on Machine Learning Research (10/2025)
Thus, when r 2 2 + 1,
B[y,
- E [|St]]
Ot
6
8
E
-
|
2
2
(25)
ad
202
2n
01,3
aK
Here, when K 221 1, have
0 5 1
-E{Y, 1.
(26)
Therefore, from the Chernoff bound,
Pr
Y
Pr
Y, < 1 -
1 [
E [rl
a
S exp
1
E [Y,]]
(27)
2
aK
(1-
1
S
exp
}
27
K
In the same way, we can prove that when r' S n - -
{
1 1)²
0 Zr S 7
aK
Pr
S exp
{
1
(28)
24
K
Thus, by defining E, to be the event "e, is allocated to a bucket with size greater than or equal to 8," from Lemma A.1
8
a
8
Pr[E,] < Pr
r 2
2
+ 1 A Y. <
[
v
r
2
A
Z,
<
8
{
< Pr
r
+1 1 A Y 3
+ Pr
rsn
A
2, 4
2
2
exp
aK
(1 }}
(<< $ +1 V r>>- -
(29)
2 exxp
ak
(1 - )
(else)
27
aK
2
1
< 2exp
27
K
Therefore,
aK (1-
1
E
1
[[E,]
2n exp
(30)
27
K
Then, noting that the number of buckets with size greater than or equal is less than or equal E 1F,,)/8,
2n
aK
(1
E IK
|csl > 8311
<
exp
(31)
2>
K
21

---

Published in Transactions on Machine Learning Research (10/2025)
Then, from Markov's inequality, we have
Pr[ji, |es > = ||,s| | > 831 2 11
2n
{ ak
2
(32)
I exp { 27
1 K
A.4 The Quantization-Aware Version of Lemma 3.4 and Theorem 3.6
In general, computers represent numbers in finite number of bits, the numbers they handle are inherently discrete. However, Theorem 3.6 which states that the expected computational complexity of PCF Learned Sort is (n log n),, does not cover discrete distributions. Here, we define the quantization process by which a computer represents numbers in finite bits and then show that the expected computational complexity of PCF Learned Sort is still On log n),, under the assumption that "the quantization is fine enough."
First, we assume the sampling and quantization process is as follows:
Assumption A.2. For range of values D (S R), define m (E N) contiguous regions D1, De..... Dm such that (i) they disjoint from each other and (ii) together they form D. For each region, determine representative values 2.....,.mmm Here, ,... are values contained in D1, D2...., Dm, respectively, For value r (E D). the quantized value of z', is obtained as z' = Tú, where i is the (only) i such that x E Dj. The value æ is sampled according to the probability density function f(z), but computer keeps x' (instead of œ) in log, m bits with some quantization error.
Also, for the interval I C D, we define (I( as follows. Definition A.3. (Z) is the maximum width of D, that intersects with interval I, i.e,,
(Z)) max ||: D + 0, =dd==1, beii=,,..., m,.
(33)
where [Da] is the width of the range D,
We can prove that (T) is the upper bound of the quantization error of in I, i.c., |E x'1 S (I() when 4 E I.
Now, the assumption that the quantization is "fine enough" is specifically defined as follows.
Assumption A.4. (Recall that our PCF Learned Sort recursively calls its own algorithm. Each time of recursion, the range of values of interest changes, and the length of the array of interest also changes.) For all I and that appear in the algorithm, the following holds:
Bn([I) 7
S 2
(34)
We show intuitively and empirically that this is a satisfactory assumption.
First, to show intuitively that this assumption is satisfactory, we give an example. Let I be a range of values that can be represented by a 64-bit double (1 bit for the sign, 11 bits for the exponent part, and 52 bits for the mantissa part), that is, I = [-1.79 x 30308 1.79 10308). The quantization performed by mapping each value the nearest number that can be represented by a 64-bit double. In this setting, (T(Z) 1.99 x 10292. [ 3.59 30008, m[I 5.55 10-17, Thus, for usual B, B 9 x 1 Equation 34 holds.
Second, we show that Equation 34 is satisfactory assumption empirically. In the 1,280 measurements, where 10 measurements each for 16 different neE {10", 2 x 10 5, x 5.23 x 107 pairs of (I, 3) appeared (we set 3 = [,²/1),, and the left. side of Equation (34 is at most 8.11 10-9, indicating that Equation (34) is always true with a margin.
10*)) on different datasets,
Under this definition and assumption about quantization, we can prove the quantization-awarc version of
Lemma 3.4
22

---

Published in Transactions on Machine Learning Research (10/2025)
Lemma A.5 (Quantization-aware version of Lemma 3.4 Let σı and d2 be respectively the lower and upper bounds of the probability densily distribulion f((x) in D, and assume that 0 < S < DC. That is, I BED DD = 01 S f(x) < 02. Also, let 1y be the array created by the quantization of x (E in the manner deftned in Assumption A.2
Then, in model-based bucketing of a'y (E In) {c;)]=1 using MrCF, the following holds for any interval I (S D) under Assumption A.4
aK' (1 (1- K' 21 7 Pr(3j,1cy] > 8| exp K = 2n 013
78
4027
1
(35)
2y
The proof of Lemma A.5 is done in the same way as Lemma 3.4 That is, we first prove the following lemma. Lemma A.6 (Quantration-awwrr version of Lemma A.G Let e' (E I") be a sorted version of a'z (E I") and A = (I'ax 3 (where I'mi and T'max are the minimum and marimum values of x'z, respectively).
Also, define the set S T as follows .r.....,,,))
Sr =(k| (mnax(1,-6621) + A + (T) Ex Se - -
- -n([I),
(36)
T l + A (T) S ek mmin(r+6/2.n) - A (T)
(37)
Using this definition, define Yjrr Zinr Yr, D3 as follows (j =1=,,.. 1,...,,
a, r 1,.
Y = (
(JE 8.) (else)
2 10
(ET,))
Y== Σ jr
Z = Σ Z/rr
(38)
(else)
If the size of the bucket to which ex, is allocated is greater than or equal to 6, then the following holds:
8 r r2
2 +
a 7
r
8 A Z
a 7 )
a
<
(39)
Proof. The proof method is exactly the same for Lemma the IDs of the buckets to which 6/+0/2 and ef are assigned,
A.1
That is, by taking the difference between
[F(C (f(6+4/2))1 +1] +1) - (1F(e))71 +1)
7 (i aj er48/2 A - (T) - -2215 aj Se, Se, + +222(()))++ +1)
7
(i |e A+ 2I( <az S Sc48//2 A (n)(
(40)
24,-1
a
20,
when >
Thus, we prove that when
8 (5= +1++1v Y 11) ^
(r>n
(r>n-5
Z >
a
(41)
2
holds, 6/-5/2 and e, assigned to the different bucket and 6/-5/2 and e, assigned to the different bucket. Then, the contraposition of the lemmna is proved.
Using Lemma A.6 can prove Lemma A.5
23

---

Published in Transactions on Machine Learning Research (10/2025)
Proof. Let q' max J /2+ fz(x (where y value such that (y. A + 2n(Z) S I). Then, from S f(x) oz for all x EI,
"
d' maxy (++++2(()
fyydd
Jz (or)de
max,, (V+)+2n(2) ozdy
SI oide
02(A + +nn(II)
(42)
01 (Fmax F'mia)
2
2 018
[
202
v "13²
The last inequality obtained by Assumption A.4
Thus, when r 2 1 1
8
E
|.5
= E
[ 5r- + A 2n( <e Se. A 2n(z)}}
2
2
E [k: 6r- ex 6, A 2n) + +EIKK er - -- 2n(I) < s setlll
(43)
ng'
+ n4'
40
0
Thus, when r 2
2
5 1,
E|Y
[|SI
a
8
8
E
2
2
(44)
ad
402a
2n 013
aK'
From this point forward, by proceeding in exactly the same way as the proof of Lemma 3.4 the following using Lemma A.I
prove
2n
aK' (1
2
K' 21
Pr le,l
5)
exp
{
(1- K"
(45)
27
Using Lomma A.5 we can prove the following theorem.
Theorem A.7 (Quntizattion-wware version of Theorem 3.6 Let σi and 02 be the lower and upper bounds,
respectively, of the probability density distribution f(x) in D, and assume that < 01 S 02 < Oc Also, assume that the input array quantized way that satisfies Assumption A.2. and Assumption A. Then, the expected complexity of PCF Leorned Sort with MPCF as the bucketing method and a 3 7 |/3/ is On log n)..
24

---

Published in Transactions on Machine Learning Research (10/2025)
Proof. When 3 = =======-- |n3/4| the computational complexity for model-based bucketing is O(n). Since K" ="= -((()) when a = 3 = 7 8 = K' 2 1 for sufficiently large n, and
2n 8
ak'
2 }
exp
On exp(-vn)) s o
(46)
27
K
log
Therefore, from Temma is On log n)...
3.3 and Temma A.5 the expected computational complexity of PCF Learned Sort
A.5 Proofs for Spline Learned Sort
Definition of Spline Learned Sort. We now formally define Spline Learned Sort, which we propose as variant of PCF Learned Sort. In particular, Spline Learned Sort replaces MPCF the bucketing method that uses PCF the CDF model-with MSpline: bucketing method based on spline-based CDF model. Below, we give rigorous description of MSpline.
The training algorithm of the CDF model in Mspline is the same as in MrCF. That is, the parameters at 3 E N are determined by n. Then, following this setting, we sample an array a of length a from the imput array x, which subsequently bin-counted (as described in Section 3.3).
For later explanation and proofs, we introduce additional terminology. We define the vector of thresholds Thus, the i-th bin during CDF model training corresponds to the interval [t,, (441). Accordingly, the non-decreasing, non- negative array b formed by bin-counting is given by b = (j E (1,....a) aj < 44111 for i = 1,2,. 1. We also denote by Fa(r) the empirical CDF of the sampled array a: Fa(z) = =if E (1,2.... a S x}1 xz]//a fa.
8 + used for counting t R t Tmin (Xmax Tmin (i 1)/8 for i= 1, ,,,
The inference algorithm of the CDF model in Mspline is similar to but slightly different from that in MPCF. In PCF, the prediction is constant within each interval (41). In contrast, the spline-based case, the prediction is obtained by linearly interpolating the empirical CDF values at the endpoints of the interval. Specifically, the output F(x) for input is obtained follows. As in PCF, we compute
(x-zmin)8 + so that E [(()): While PCF returns Fa Fa(li())11) = baaa/a the CDF prediction, the spline-based method linearly interpolates between Fa (ta(a))) and Fa Fa(t(())1):
i(x) Amax-Bmmn
x - ti(x)
F(x) Fa(ti())) + ((xx)11 - 14x))
(Fa(ti(a)2)) F (t(t()))))
(47)
= (1())-1+ ((x))11 tz(x))
ti(a) -t(aa . (bi(s) - bo(z))1))
(48)
with bo = O.
Unlike PCF, which only considers which bin a value falls into, the polino-based method also accounts for the relative position of the value within the bin to compute the predicted CDF F(x). The asymplotic computational complexity for training and inference is the same as PCF: O(n) for training and O(1) per element for inference. However, unlike PCF (which only requires array lookups), the spline-based approach requires additional subtractions and multiplications during inference, leading a larger constant factor in runtime.
Theorems Guaranteeing the Complexity of Spline Learned Sort. When Mspline is used as the bucketing method in our learned sort framework, the same complexity guarantees as in PCF Learned Sort hold. In particular, we obtain the following worst-case guarantee (Theorem) A.8) and expected-case guarantee (Theorem A.9.
Theorem A.8 (Spline version of Theorem 3.5 If Mspline is the bucketing method, the worst-case complerity of the standard sort is (n)((n)) (where (n)) a decressngg function), and a = ? = |In //// then the worst-case complerity of Spline Learned Sort is (nU log log...
Proof. The proof is identical to that of Theorem 3.5
using Lemma
3.1
25

---

Published in Transactions on Machine Learning Research (10/2025)
Theorem A.9 (Spline version of Theorem 3.6
Let di and 02 be the lower and upper bounds, respectively, of the probability densily f(a:) on D, and assume O < I 02 < xc. If MMsllnne is the bucketing method, the expected complexity of the standard sort is (n log n), and = 3 = = = =nn//J, then the expected
complerity of Spline Leorned Sort is On log l).
To prove this theorem, we first establish the following lemma.
Lemma A.10 (Spline version of Lemma A.1 Define e. Tr, Yrr, Zyrs Y,, Z, exactly as in Lemma A.1 ..). That is, let e E I be the sorted version of aı T and set A = (Fmax "min 3BB (where Tuin and max are the minimum and marimam values of æι, respectively). Also define
r r= (j=1....,.0
S. [k: Cmax(1,r-8/22 + A ck sc -),,
T [k l + AS Ck (min(r+8/22a) 4}
(49)
and
{ (JES,) 0 (otherwise)
230=10 - { -0
(T
Ysr
Zjr
Y, = E Ygm
Z, Z, Z
==
(50)
(otherwise)
j=1
5=1
When using MSplines if the size of the bucket to which er is assigned is at least 8, then the same condition holds; namely,
as in Equation 19
rr 2 _ +
Y
(r
nn
A
2 1
(51)
Proof. The proof proceeds exactly
as in Lemma A.1 by contraposition. That is, assume
r <<< +1 V Y > 1:1) A
r>
Zr
> [
1g),, and prove that e, is assigned to a bucket smaller
than 8.
First, we show that er and (mim(++6/2,n+1) are assigned to different buckets. As in the proof of Lemma A.1 the case n - 5822 < S n is immediate; hence we focus on r S n - 6/2. The bucket ID of e, is [F(e,) +1, while that of c,4//2 is (((r44//))]]11 By the definition of the spline-based CDF model and the incqualities l((e))1 Se, er + A, Vi(er1192) 2 Cr+6/2 A, we obtain
S 1 H[ aj Se+ F(cr+8/2) 2 Fa Fa(ti((,=s)a) = {j aj S t((0441/2))
F(er) S Fa(l((e))+)) = _ |0 aa S (ete)
(52)
[ |a S cr/8/2 A//.
(53)
Hence, their bucket IDs satisfy
[F()) +1 [6 aj se+ +
(54)
[F(c,48/2)1 +1> {j ag S Cr+6/2 A}|
(55)
which are identical to Equations 20 and 21 Thus,
(L((e44/2)))+ +11) - (LF(e. + +1) 0,
(56)
and hence and 6r+5/2 are assigned to different buckets.
By a symmetric argument, (max(0.r-6/2) and e, are also assigned to different buckets. Therefore, the bucket containing & has size at most 8 - 1, completing the contraposition.
From Lemma A.10 we obtain the following theorem.
Theorem A.11 (Spline version of Temma 3.4h. Let o, and 02 be the lower and upper bounds of the probability density fxx on D, and assume 0 < 01 S 02 < 0o (i.e., α1 S f(x) S 02 for all E D). Then, in model-based
bucketing of x I inlo {c;))=1
7+1 using Mspline; the following holds for any interval I D:
K == 76
2027
2n
exp {
aK (1
Pr(3i, 1cy 8 S
(57)
2n
2y
Proof. The proof is identical to that of Lemma 3.4 using Lemma
A.10
26

---

Published in Transactions on Machine Learning Research (10/2025)
Table 1: Statistics of real-world datasets used in our experiments.
Dataset
Size
# Unique Values
% of Duplicates
Chicago
Start] Chicago 2021
19,588,772
216,610
99.45
Chicago
Tot]
Coicago
2021
39,199,154
6,887
99.98
NYC PPcckup
nyc 2020
100,000,000
26,666,741
73.33
NYC
[Dstt]
Inyc 2020
200,107, 656
2,060
100.00
NYC
[Tot] Inyc
2020
199,964, 9944,499
7,428
100.00
SOF
Humidity
Mavrodiey
2019
96,318, 8,228
8,128
99.99
SOF
Pressure]
MMavrodiev
2019
96,317,180
862,502
99.10
SOF
Temperature
Mavrodiev
2019
96,432,856
5,638
99.99
Wiki
Marcus
2020
200,000, 000
90,437,01 111,
54.78
OSM
Marcus et al.
2020
800,000, ,000
799 469,
469,199, 195
0.07
Books
Marcus et al
2020
800,000,000
799,99 99,,9994,9
0.00
Face
larcus et al.
2020
199,998,000
199, 99,,998,000 000
0.00
Stocks
Volume
Onyshchak
2020
27,596,686 686
325, 654
98.82
Stocks
Open]
Onyshchak
2020
27,596,686
830,758
96.99
Stocks
Date
Onyshchak
2020
27,596,688 686
14,646
99.95
Stocks
Low]
Onyshchak
2020
27,596 686
863,701
96.87
Finally, using Theorem A.11
we can prove Theorem A.9
Proof of Theorem
4.9
The proof follows exactly the same steps as Theorem 3.6 applying Theorem A.1l
to
Lemma 3.3
B Real Dataset Details
In the main text, we provided only a concise list of the real datasets used in our experiments. Here we describe each dataset in more detail.
The Chicago Taxi Trips dataset includes taxi trips reported to the City of Chicago in its role as a regulatory agency over the last six years. The data to be sorted includes trip starting timestamps and lotal fare amounts.
Chicago [Start, Tot]:
NYC [Pickup, Dist, Tot]:
The New York City yellow taxi trip dataset includes trip pickup datetimes, trip distances, and total fare amounts.
SOF [Humidity, Pressure, Temperature): The Sofia dataset contains time-series air quality metrics (humidity, pressure, and temperature) measured at 1-minute intervals from outdoor sensors in Sofia, Bulgaria.
Wiki: The Wikipedia dataset contains article edit timestamps Marcus et al. 2020
OSM: Uniformly sampled OpenStreetMap locations represented as Google S2 CellIds (Mareus et al. 2020
Books: Book sale popularity data from Amazon Marcus et al. 2020
Face: The FB dataset contains an upsampled set of Facebook user IDs obtained via random walks
on the FB social graph (Marcus al.) 2020). As in (Kristo al. 2021a Ferragina & Odorisio,
2025), the outliers greater than the 0.99999 quantile are discarded.
Stocks [Volume, Open, Date, Low]: The Stocks dataset contains historical daily opening, low prices, trading volumes, and dates for all NASDAQ tickers (stocks and ETFs), retrieved via the yfinance Python package up to April 1, 2020.
27

---

Published in Transactions on Machine Learning Research (10/2025)
Unitorm
Narmal
Exponential
Lognormal
Chicago [Start]
Chicago (lot)
Timne (S) m
Time (5)
Dendity
Deriltt
Denety
Dongity
Value
Value NYC Dist)
Value NYC (Tot)
Value
Value
Value
NYC Pickupl
SOF (Humidity)
124
5DF Pressure
50F [Tmpeeaturr
Tmm 697 69/00
mi (8
mime (5
Time
Dersty
Derdit
Deraty
3000
Valuu
Value OSM
Value Books
Value Face
Value
Value
Wiki
lime m
Tinna /s/n
Learned (Proposed)
Sp Learned (Proposed)
Dunaty
Denetty
Density
Dunilly
std::sort
Sort
Vilue Stocks (V ume]
Stocks Open
Value Stocks Datel
Value Stocks Low)
IS4o (Axtmann al., 2017)
Learned 2.0 (Kristo et al., 2021)
Time 18 /
lime (5)
[S]
Time [S
(Ferragina ai., 2025)
(Ferragina al., 2025)
Learned Sort 2:1 (Ferragina 2025)
Dergty
Deroity
Vilum
Value
Value
Vilum
Figure 5: Time to sort the array in adversarial environments. Below each graph is histogram that visualizes the distribution of each dataset. The standard deviation of the 10 measurements is represented by the shaded area.
Furthermore, the detailed statistics of these datasets, including their sizes, the number of unique values, and the percentage of duplicates, are summarized in Table 1 The percentage of duplicates is computed as 100 x (1- Lniquee_ valuees where n is the total number of elements and unique values is the set of distinct elements. In particular, for several datasets (Chicago [Start, Tot], NYC [Dist, Tot], SOF [Humidity, Pressure, Temperature], and Stocks [Volume, Open, Date, Low]), the number unique values is extremely small, accounting for less than 3.2% of the total elements.
C Experiments in Adversarial Environments
To evaluate the robustness of our Learned Sort, we conducted experiments under adversarially constructed inputs that explicitly violate the assumptions of Lemma 3.3 Specifically, given an original dataset. of size n, we injected n duplicate elements a randomly chosen value inside the range [zmin xmax]. where Emin and mmax the minimun and maximum value of the input array æ. As a result, the array length doubled to 2n, and the constructed distribution contained a point mass of probability one-half, leading huge probability yensity that value. This setting intentionally breaks the assumption 02 required in Lemma 3.3
28

---

Published in Transactions on Machine Learning Research (10/2025)
Figure 5 reports the sorting time such adversarial datasets. The results show that the expected bound of On log log n) for our PCF Learend Sort no longer holds once the assumptions are violated, and the performance of PCF Learned Sort occasionally degrades to the level of : :ort.. However, we consistently observed that PCF Learned Sort never exceeded the worst-case complexity of O(n log n), and thus its runtime std::sors
remained comparable
On the other hand, we found that Learned Sort 2.0 (Kristo al, 2021b). which has Onn2) worst-case complexity, sometimes exhibited severe slowdowns. For example, on data of size n 10y sampled from Normal distribution with injected duplicates, the sorting time of Learned Sort 2.0 reached up to 10.89 seconds, whereas PCF Learned Sort required at most 0.021 seconds.
We also found that BLS, ULS, and Learned Sort 2.1 (Ferragina & Odorisio 2025 which also have (n)²) worst-case complexity, sometimes exhibited substantial performance degradation. For example, on data of size n 10 sampled from Normal distribution with injected point masses, Learned Sort 2.1 took up 0.154 seconds, compared with 0.042 seconds for PCF Learned Sort and 0.078 seconds for std: :sort.
These results highlight the fragility of sorting algorithms without strong worst-case complexity guarantees, limitation shared by many cxisting learned sorting algorithms. They underscore the importanco of developing learned sorting algorithms-ase such as our PCF Learned worst-case complexity guarantees.
combine practical efficiency with rigorous
D Runtime Profiling
To better understand the practical behavior of PCF Learned Sort, we profiled the runtime of its major components: (i) model training, (ii) bucketing, (ii) standard sort applied to buckets that are too small (< r), and (iv) standard sort applied to buckets that are too large (2 6). The results are shown in Figure
For small input sizes n, the majority of the runtime is typically spent on applying the standard sort buckets smaller than As increases, the relative cost shifts, and most of the runtime is instead consumed by the bucketing stage. Model training remains consistently lightweight, comparable to or faster than bucketing, and never exceeds roughly one quarter of the total runtime. Thus, training does not become the dominant factor in practice.
Figure 7 shows the results for adversarially clustered inputs (as described Appendix C Under the adver- sarial setting, the bucketing algorithm more frequently produces large buckets, which are then handled by standard sort. In these cases, a larger fraction of the runtime is attributed to this fallback mechanism.
Overall, these analyses clarify which components of PCF Learned Sort dominate the runtime under different conditions. They also highlight that the algorithm adapts graccfully: training and bucketing scale well, while the worst-case fallback ensures robustness without catastrophic slowdowns.
29

---

Published in Transactions on Machine Learning Research (10/2025)
Uniform
Norma
Exponentia
Lognormal
Chicago (Start]
Chicago [Tt
Time Ratio [%6
Time A0100 1%
Time Rotio [S]
Time Retio [%]
Time Ratio (%6
10
18
131
Denaty
Densiy
Denaty
Dersity
Value NYC (Pickou
Value NYC (Dist)
Value NYC (Tat
Value
Value
Vi
SOF [Humidity]
SOF Pressure
SOF [Temperature)
Time Ratio (56)
Time Rotio (56)
Time Ratio 1%d
Time Ratio [16
Ratto
Dersity
Denatty
Deriity
Valuue Wiki
Value OSM
Valuo Books
Welue Fare
Velue
Ve
Timee Ratio [Sc
Ratio [%]
[%]
Time Rotio (%]
Denatty
Denstty
Danaly
Denily
Std Sort (n < T)
Train PCF
Value
Value
Value
Value Stocks Low
Scocks [Volume]
Stocks [Ooen]
Stocks (Dote]
Assign Buckets
Time Ratio 1%6)
Timle Ratio 1%
Tim Saro [%]]
Tine Rotio [%]
10
Value
Vilue
Viluo
Wiluo
Figure 6: Breakdown of runtime components in PCF Learned Sort. The total runtime is decomposed into (i) model training, sort applied to buckets larger than 5.
(ii) bucketing, (iii) standard sort applied to buckets smaller than т, and (iv) standard
30

---

Published in Transactions on Machine Learning Research (10/2025)
Uniform
Exponential
Lognormal
Chicago [Start]
Chicago [Tot]
Time Ratio 1%)
Time Ratio (%]
Tirre Ralio [%]]
Time Ratio [X]
Time Ratio (%)
Time Ratio (%)
Dendyy
Dembty
Dansty
Dundty
Densty
Densty
Value NYC [Pickup]
Value
Value NYC [Tet]
Value
Value
Value
NYC [Dist]
[Humidity]
50F (Pressure)
5OF [Temaeraturr
Time Ratio 1%6
Time Ratio 1%)
Time Natio (96]
Time Ratio 196]
Time Ratio (9)
Time Ratio (%)
12
1
Densty
Demdyy
Densty
Dunaty
Value
Volue
Value Books
Value Face
Volue
Value
Time Ratio 196]
Time Ratio 1%)
Fire Natio 1%6]
Tire Ratio [96]
11
11
Densty
Densty
Denoty
Dendty
Std Sort (n < t)
Value
Value
Value
Value Stocks [Low]
Train PCF
Stocks No ume]
Snocks [Open]
Stocks (Date]
Assign Buckets
Time Ratio 1%)
Time Ratlo [%)
line Katio [X]]
Time Nalio [X]]
Std Sort
10
Denoty
Densty
Denery
Value
Value
Value
Value
Figure 7: Breakdown of runtime components in PCF Learned Sort in adversarial environments. The total
runtime is decomposed into (i) model training, (ii) bucketing, (iii) standard sort applied to buckets smaller than and (iv) standard sort applied to buckets larger than ó.
31


Reviews:
[{"review_id": "niQnruvta4", "reviewer": "Reviewer_MsJR", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n\nTheoretical Foundations: The paper provides strong theoretical guarantees for the PCF Learned Sort algorithm. Lemmas and theorems with detailed proofs (summarized in the main text) formally bound both expected and worst-case complexity ($\\mathcal{O}(n \\log \\log n)$ and $\\mathcal{O}(n \\log n)$, respectively). This addresses a significant gap in the learned sort literature, where prior works often lacked formal complexity analysis beyond empirical speedups.\n\nClarity and Reproducibility: The methodology section is well-organized, with Algorithm 1 and Figure 1 clearly outlining the recursive bucketing and CDF model process. \n\nEmpirical Evaluation: The experimental section demonstrates careful benchmarking: comparisons with quick sort on diverse synthetic (uniform, normal, exponential, lognormal) and real-world datasets (NYC, Wiki, OSM, Books) are presented. Figures 2–9 show operation-count-per-$n$ curves as input size scales, illustrating the sub-linear overhead. The detailed use of operation count rather than wall-clock time is a good choice to control for hardware dependencies.\n\nPractical Relevance: By empirically evaluating performance and relating observed behaviors to distributional properties (e.g., the $\\sigma_2/\\sigma_1$ ratio), the paper explains real-world speedups (or slowdowns), deepening the practical insight for scenarios in which learned sorts would be most effective.\n\nExperimental Support for Theoretical Claims: The results in Figures 18–23 (bucketing failure rate heatmaps) systematically map parameter configurations to failure probabilities, directly validating the theoretical lemma bounding bucketing failure.\nPositioning Within Existing Literature: The paper references key works on learned sorts, learned indexes, and both comparison-based and distribution-based sorting. There is also acknowledgment of sample sort theory and learning-augmented algorithms, referencing appropriate classical and recent literature.\n\nWeaknesses\n\nOverall, I think the writing can substantially be improved with first formally defining all notations. For instance section 3.1 introduces the method overview with no context about model-based bucketing.\n\nSection 4.1 discusses the default sorting algorithm when bucket size falls out of range as Quicksort while in the diagram its shown as IntroSort. Maybe this can be cleared better\n\nLimited Related Work DIscussion: Several directly relevant recent works on parallel learned sorting (e.g., Carvalho, 2022; Carvalho & Lawrence, 2023) and advanced sample sort baselines (e.g., Axtmann et al., 2017) are not adequately discussed nor cited, despite their strong relevance for both empirical and theoretical positioning. Their omission makes the literature review appear less than comprehensive, and may leave readers with an incomplete sense of prior art, particularly regarding scalability or parallelization concerns.\n\nBaselines Limitation in Experimental Section: The experiments only compare PCF Learned Sort against quick sort. This reduces clarity around experimental advances over the strongest prior methods, making it difficult to judge the practical gap or performance trade-offs versus state-of-the-art.\n\nAssumptions Not Always Fully Justified: The main theoretical result holds under a bounded probability density ($0 < \\sigma_1 \\leq f(x) \\leq \\sigma_2 < \\infty$), but there is limited discussion about the prevalence of such distributions in real-world data. The limitation section acknowledges this, but further empirical exploration—e.g., testing in more skewed or heavy-tailed settings—would strengthen understanding of robustness.\n\nLack of Expressiveness in CDF Model Choices: The paper settles on piecewise constant approximation, but does not deeply analyze or experiment with other popular CDF models (e.g., neural CDFs, histograms of differing bin widths, spline-based models). There is little evaluation of trade-offs between PCF and other learned models, which could further improve empirical performance or robustness.\nNo Exploration of Parallelism or Scalability: The design and analysis is restricted to sequential settings; there is no discussion (theoretical or experimental) of parallelization potential, memory overhead, or multi-core scaling, all of which have been central for modern sort implementations.\n\nNo Analysis of Model Training Costs: There is a brief acknowledgement that model training is factored into the complexity, but the impact of training time relative to inference/bucketing is not explored experimentally, which is practical for real-world high-throughput sorting.\nInsufficient Dataset Diversity: While several real datasets are used, broader inclusion of highly skewed, real-world distributions (not just OSM/Books, which are discussed) would help assess generality.\n\nNo Discussion of Learning-Augmented Adversarial Robustness: There is no theoretical or experimental exploration of cases where the input distribution may be adversarial or poorly approximated by the CDF model, which would reveal algorithmic risk in edge cases.\nFigure- and Table-Specific Commentary\n\nFigure 1 (Algorithm diagram): Visually and conceptually clarifies the recursive bucketing, the CDF model’s role, and where recursion stops in favor of classical sorts. The right-side inset with the empirical vs. model CDF is especially useful for seeing the effect of a PCF.\nFigures 2–9 (Experimental results): These plots concisely show the number of operations per input length across data regimes. The gap between PCF Learned Sort and quick sort is almost constant (flat curve) for PCF, versus the growing curve for quicksort, directly evidencing sub-$n \\log n$ scaling.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper presents PCF Learned Sort, a learned-augmented sorting algorithm with theoretical guarantees on the running time. By utilizing a piecewise constant function (PCF) to approximate the cumulative distribution function (CDF) of input data, the algorithm constructs recursive, model-based buckets to sort arrays efficiently. The main theoretical result is that under mild assumptions on the data distribution, the expected time complexity of the algorithm is proven to be $\\mathcal{O}(n \\log \\log n)$, with a worst-case guarantee of $\\mathcal{O}(n \\log n)$. Extensive experiments on both synthetic and real datasets empirically validate the theoretical findings and provide insight into the algorithm’s performance as influenced by data distribution properties.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Potentially Missing Related Work\nCarvalho, I. (2022): \"Towards Parallel Learned Sorting\"\nThis paper addresses parallelization of learned sorting algorithms, which is relevant for analyzing scalability and memory usage. It should be referenced and briefly discussed in the context of future work or in the comparison to state-of-the-art scalability.\nAxtmann, M., Witt, S., Ferizovic, D. (2017): \"In-Place Parallel Super Scalar Sample Sort (IPS4o)\"\nAs one of the most efficient sample sort implementations, this should be included as a baseline and in the related work section. Empirical results and theoretical comparisons to this method are essential, particularly given the sample sort inspiration for the PCF Learned Sort.\nCarvalho, I., Lawrence, R. (2023): \"LearnedSort as a Learning-Augmented SampleSort: Analysis and Parallelization\"\nThis paper analyzes and parallelizes LearnedSort, offering direct theoretical and empirical comparisons. It should be discussed in relation to both theoretical analysis approaches and practical implementations.\nPaolo Ferragina et al. (2025): \"FL-RMQ: A Learned Approach to Range Minimum Queries\"\nRelevant for framing the increasing prevalence of learned algorithmic approaches. Inclusion in related work would contextualize the broader field of learning-augmented data structures.\nLi, Y., Gimeno, F., Kohli, P. (2020): \"Strong Generalization and Efficiency in Neural Programs\"\nTheir investigation of strong generalization properties in learned algorithms could inform discussion about the theoretical underpinnings of learned sort generalizability, meriting a brief mention.\nSadakane, K. (2007): \"Compressed Suffix Trees with Full Functionality\"\nThe foundational concepts around compressed data structures with functional guarantees may provide useful context in the related work.\nSato, A., Matsui, Y. (2024): \"Fast Construction of Partitioned Learned Bloom Filter with Theoretical Guarantees\"\nThis work could be mentioned to frame the authors’ broader agenda in learning-augmented data structures and theory.\n\nAlso address the concerns from weaknesses. \n\nQuestions\nHow would PCF Learned Sort compare against modern parallel sample sort implementations and learning-augmented sorts (such as IPS4o, or recent parallel LearnedSort variants)? Would inclusion of such baselines significantly impact your quantitative findings?\n\nCould you clarify the typical prevalence of the required distributional assumption ($0<\\sigma_1\\leq f(x)\\leq\\sigma_2<\\infty$) in practical, large-scale datasets? Are there natural, widely arising scenarios where this fails, and if so, could the algorithm or theory be adapted?\n\nIs there scope (and associated theory) for substituting the PCF with more expressive or data-adaptive CDF models (e.g., splines, neural networks) in this framework? Have you tried such models, and how do they fare empirically or theoretically?\n\nAre there any plans for public release of source code, and can you comment on practical implementation nuances such as memory usage or multi-core scaling?\n\nIn adversarial or model-mismatch settings (e.g., highly clustered or adversarially constructed data), does the bucketing lemma still hold, or do worst-case time complexities appear empirically even for non-pathological but practical datasets?\n\nScore Sensitivity:\nMy rating could be increased substantially by (a) comparing against stronger, modern learned and classic sort baselines, (b) more thoroughly addressing adversarial, high-skew, and \"edge case\" distributions both empirically and theoretically, and (c) extending the analysis to parallel multi-threaded scenarios, which are critical for modern large-scale sorting.", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "TplyYD5aXf", "reviewer": "Reviewer_djyS", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "# Strengths\n\n- The writing is quite easy to follow: motivation and related work is relatively well written\n- Algorithm is easy to understand\n- Proofs are well structured and there is sufficient exposition to discuss assumptions and what the lemmas are trying to do\n- Empirical evaluation is performed against natural competitors to the proposed method\n\n# Weaknesses\n\n- The authors only mentioned that PCF has worst case complexity of $O(n \\log n)$ much later and kept emphasizing on the expected complexity of $O(n \\log \\log n)$. While reading Sections 1 and 2, I was under the illusion that it was outperforming the worst case complexity of prior sorting algorithms but it turns out that its worst case complexity of $O(n \\log n)$ is even worse than some other prior work mentioned: $O(n \\sqrt{\\log n})$ (Han, 2020).\n- I feel that Assumption 3.2 is more or less \"doing all the work\" in enabling PCF. It feels like a very strong assumption and it is unclear why prior methods cannot obtain or beat $O(n \\log \\log n)$ if they are also given such an assumption to operation on. For example, if the worst case $O(n \\sqrt{\\log n})$ algorithm (Han, 2020) could achieve expected complexity of $O(n \\log \\log n$) under Assumption 3.2, then wouldn't PCF be \"strictly dominated\"? Note that, in the spirit of TMLR, I am *not* saying that the claims related to PCF is false.\n- I understand that prior work (Zeighami & Shahabi, 2023) compared the number of basic operations and so this is why the authors also compared using that metric. However, I believe that it is the wall-clock-time that will eventually determine whether an algorithm will be adopted in practice. Unfortunately, on the wall-clock-time metric (Figure 4), PCF is not the fastest algorithm in any of the experiments and across different array sizes.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proposes a learning-augmented sorting algorithm called PCF Learned Sort with a worst case complexity of O(n log n) and expected complexity of O(n log log n) when the data elements are assumed to be drawn iid from some underlying unknown but bounded distribution (Assumption 3.2 + the bounds imposed by $\\sigma_1$ and $\\sigma_2$). On a high-level, the algorithm works by recursively bucketing elements while \"training\" a new CDF predictor at each step. Theoretical analysis is given and experiments were conducted to empirically compare the proposed algorithm against Quick Sort, Radix Sort and Learned Sort.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- PCF is first defined on Page 4 while the acronym has been used since Page 1. It would be nice if \"Piecewise Constant Function\" can be mentioned at the very first time \"PCF\" is used\n- I'm a little confused by some part of the experiments. As you divide by $n$ in empirical plots and \"the graph of quick sort is almost linear\", are you suggesting that Quicksort runs empirically $n^2$ in your experiments?", "broader_impact_concerns": "I do not foresee any broad ethics/impact concerns for this paper.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "fBg8v6eULB", "reviewer": "Reviewer_FqdB", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\nThe main theorem is amazing.\n\nThe experiments are being run on a home computer.\nThis is good and reinforces reproducibility :)\n\nWeaknesses:\nDo the experimental inputs violate the assumptions of their main (conditional) theorem?\n(This is important, as the experiments should aim for the setting that is **not** covered by the assumptions, so that we can see what happens when running the algorithm in the wild.)\nI am not sure whether the authors clearly state that :)", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors show a sorting algorithm that utilizes some machine learning \"pre-processing.\"\nThe idea is not new, but well implemented.\nThe main contribution is as follows:\nThe authors bound the run-time of their sorting algorithm by $O(n \\log \\log n)$ (expected), whenever some mild --- but not trivial --- conditions are met in the input distribution.\nMoreover, they give some experimental evidence to strengthen their main points.\nI think this is an interesting paper and definitely merits acceptance.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please address the \"Weaknesses.\"\n\nAlso, can you please further explain why you use STANDARD-SORT for big buckets?\nThis is a bit counterintuitive, I think.", "broader_impact_concerns": "None.\n\n(Side note: I only had a quick check of the appendices.)", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)