@article{10.1093/comjnl/5.1.10,
title = {Quicksort},
author = {Hoare, C. A. R.},
year = 1962,
month = jan,
journal = {The Computer Journal},
volume = {5},
number = {1},
eprint = {https://academic.oup.com/comjnl/article-pdf/5/1/10/1111445/050010.pdf},
pages = {10--16},
issn = {0010-4620},
doi = {10.1093/comjnl/5.1.10},
abstract = {A description is given of a new method of sorting in the random-access store of a computer. The method compares very favourably with other known methods in speed, in economy of storage, and in ease of programming. Certain refinements of the method, which may be useful in the optimization of inner loops, are described in the second part of the paper.}
}
@article{axtmannInPlaceParallelSuper2017,
title = {In-{{Place Parallel Super Scalar Samplesort}} ({{IPSSSSo}})},
author = {Axtmann, Michael and Witt, Sascha and Ferizovic, Daniel and Sanders, Peter},
editor = {Pruhs, Kirk and Sohler, Christian},
year = 2017,
journal = {LIPIcs, Volume 87, ESA 2017},
volume = {87},
pages = {9:1-9:14},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f\"ur Informatik},
issn = {1868-8969},
doi = {10.4230/LIPICS.ESA.2017.9},
urldate = {2026-05-17},
abstract = {We present a sorting algorithm that works in-place, executes in parallel, is cache-efficient, avoids branch-mispredictions, and performs work O(n log n) for arbitrary inputs with high probability. The main algorithmic contributions are new ways to make distribution-based algorithms in-place: On the practical side, by using coarse-grained block-based permutations, and on the theoretical side, we show how to eliminate the recursion stack. Extensive experiments shw that our algorithm IPSSSSo scales well on a variety of multi-core machines. We outperform our closest in-place competitor by a factor of up to 3. Even as a sequential algorithm, we are up to 1.5 times faster than the closest sequential competitor, BlockQuicksort.},
copyright = {Creative Commons Attribution 3.0 Unported license, info:eu-repo/semantics/openAccess},
isbn = {9783959770491},
langid = {english},
keywords = {branch prediction,comparison-based sorting,in-place algorithm,parallel sorting,shared memory}
}
@article{biggarExperimentalStudySorting2008,
title = {An Experimental Study of Sorting and Branch Prediction},
author = {Biggar, Paul and Nash, Nicholas and Williams, Kevin and Gregg, David},
year = 2008,
month = jun,
journal = {ACM Journal of Experimental Algorithmics},
volume = {12},
pages = {1--39},
issn = {1084-6654, 1084-6654},
doi = {10.1145/1227161.1370599},
urldate = {2026-05-17},
abstract = {Sorting is one of the most important and well-studied problems in computer science. Many good algorithms are known which offer various trade-offs in efficiency, simplicity, memory use, and other factors. However, these algorithms do not take into account features of modern computer architectures that significantly influence performance. Caches and branch predictors are two such features and, while there has been a significant amount of research into the cache performance of general purpose sorting algorithms, there has been little research on their branch prediction properties. In this paper, we empirically examine the behavior of the branches in all the most common sorting algorithms. We also consider the interaction of cache optimization on the predictability of the branches in these algorithms. We find insertion sort to have the fewest branch mispredictions of any comparison-based sorting algorithm, that bubble and shaker sort operate in a fashion that makes their branches highly unpredictable, that the unpredictability of shellsort's branches improves its caching behavior, and that several cache optimizations have little effect on mergesort's branch mispredictions. We find also that optimizations to quicksort, for example the choice of pivot, have a strong influence on the predictability of its branches. We point out a simple way of removing branch instructions from a classic heapsort implementation and also show that unrolling a loop in a cache-optimized heapsort implementation improves the predicitability of its branches. Finally, we note that when sorting random data two-level adaptive branch predictors are usually no better than simpler bimodal predictors. This is despite the fact that two-level adaptive predictors are almost always superior to bimodal predictors, in general.},
copyright = {https://www.acm.org/publications/policies/copyright\_policy\#Background},
langid = {english}
}
@article{blellochPrefixSumsTheir2018,
title = {Prefix Sums and Their Applications},
author = {Blelloch, Guy E.},
year = 2018,
month = jun,
pages = {1294199 Bytes},
publisher = {Carnegie Mellon University},
doi = {10.1184/R1/6608579},
urldate = {2026-05-17},
abstract = {Abstract: "Experienced algorithm designers rely heavily on a set of building blocks and on the tools needed to put the blocks together into an algorithm. The understanding of these basic blocks and tools is therefore critical to the understanding of algorithms. Many of the blocks and tools needed for parallel algorithms extend from sequential algorithms, such as dynamic-programming and divide-and-conquer, but others are new. This paper introduces one of the simplest and most useful building blocks for parallel algorithms: the all-prefix-sums operation. The paper defines the operation, shows how to implement it on a P-RAM and illustrates many applications of the operation.In addition to being a useful building block, the all-prefix-sums operation is a good example of a computation that seems inherently sequential, but for which there is an efficient parallel algorithm."},
copyright = {In Copyright},
keywords = {Other information and computing sciences not elsewhere classified}
}
@article{blumofeSchedulingMultithreadedComputations1999,
title = {Scheduling Multithreaded Computations by Work Stealing},
author = {Blumofe, Robert D. and Leiserson, Charles E.},
year = 1999,
month = sep,
journal = {Journal of the ACM},
volume = {46},
number = {5},
pages = {720--748},
issn = {0004-5411, 1557-735X},
doi = {10.1145/324133.324234},
urldate = {2026-05-17},
abstract = {This paper studies the problem of efficiently schedulling fully strict (i.e., well-structured) multithreaded computations on parallel computers. A popular and practical method of scheduling this kind of dynamic MIMD-style computation is ``work stealing,'' in which processors needing work steal computational threads from other processors. In this paper, we give the first provably good work-stealing scheduler for multithreaded computations with dependencies. Specifically, our analysis shows that the expected time to execute a fully strict computation on P processors using our work-stealing scheduler is T 1 / P + O ( T {$\infty$} , where T 1 is the minimum serial execution time of the multithreaded computation and ( T {$\infty$} is the minimum execution time with an infinite number of processors. Moreover, the space required by the execution is at most S 1 P , where S 1 is the minimum serial space requirement. We also show that the expected total communication of the algorithm is at most O ( PT {$\infty$} ( 1 + n d ) S max ), where S max is the size of the largest activation record of any thread and n d is the maximum number of times that any thread synchronizes with its parent. This communication bound justifies the folk wisdom that work-stealing schedulers are more communication efficient than their work-sharing counterparts. All three of these bounds are existentially optimal to within a constant factor.},
langid = {english}
}
@book{cormenIntroductionAlgorithms2022,
title = {Introduction to Algorithms},
author = {Cormen, Thomas H. and Leiserson, Charles Eric and Rivest, Ronald L. and Stein, Clifford},
year = 2022,
edition = {Fourth edition},
publisher = {The MIT Press},
address = {Cambridge, Massachusett},
abstract = {"The leading introductory textbook and reference on algorithms"--},
isbn = {978-0-262-04630-5},
lccn = {QA76.6 .C662 2022},
keywords = {Computer algorithms,Computer programming}
}
@book{devroyeNonUniformRandomVariate1986,
title = {Non-{{Uniform Random Variate Generation}}},
author = {Devroye, Luc},
year = 1986,
publisher = {Springer New York},
address = {New York, NY},
isbn = {978-0-387-96305-1 978-1-4613-8643-8},
langid = {english}
}
@misc{DrDobbsJournala,
title = {Dr. {{Dobb}}'s {{Journal February}} 1998: {{The Flashsort1 Algorithm}}},
urldate = {2026-05-17},
howpublished = {https://www.neubert.net/Flapaper/9802n.htm},
file = {/home/mohammad/Zotero/storage/USYTDTCG/9802n.html}
}
@misc{edelkampBlockQuicksortHowBranch2016,
title = {{{BlockQuicksort}}: {{How Branch Mispredictions}} Don't Affect {{Quicksort}}},
shorttitle = {{{BlockQuicksort}}},
author = {Edelkamp, Stefan and Wei{\ss}, Armin},
year = 2016,
month = jun,
number = {arXiv:1604.06697},
eprint = {1604.06697},
primaryclass = {cs.DS},
publisher = {arXiv},
doi = {10.48550/arXiv.1604.06697},
urldate = {2026-05-17},
abstract = {Since the work of Kaligosi and Sanders (2006), it is well-known that Quicksort -- which is commonly considered as one of the fastest in-place sorting algorithms -- suffers in an essential way from branch mispredictions. We present a novel approach to address this problem by partially decoupling control from data flow: in order to perform the partitioning, we split the input in blocks of constant size (we propose 128 data elements); then, all elements in one block are compared with the pivot and the outcomes of the comparisons are stored in a buffer. In a second pass, the respective elements are rearranged. By doing so, we avoid conditional branches based on outcomes of comparisons at all (except for the final Insertionsort). Moreover, we prove that for a static branch predictor the average total number of branch mispredictions is at most \${$\varepsilon$}n \textbackslash log n + O(n)\$ for some small \${$\varepsilon\$$} depending on the block size when sorting \$n\$ elements. Our experimental results are promising: when sorting random integer data, we achieve an increase in speed of 80\% over the GCC implementation of C++ std::sort. Also for many other types of data and non-random inputs, there is still a significant speedup over std::sort. Only in few special cases like sorted or almost sorted inputs, std::sort can beat out implementation. Moreover, even on random input permutations, our implementation is even slightly faster than an implementation of the highly tuned Super Scalar Sample Sort, which uses a linear amount of additional space.},
archiveprefix = {arXiv},
keywords = {Computer Science - Data Structures and Algorithms},
file = {/home/mohammad/Zotero/storage/JAPPYAEU/Edelkamp and Weiß - 2016 - BlockQuicksort How Branch Mispredictions don't affect Quicksort.pdf;/home/mohammad/Zotero/storage/9BTFXAD4/1604.html}
}
@inproceedings{frigoCacheobliviousAlgorithms1999b,
title = {Cache-Oblivious Algorithms},
booktitle = {40th {{Annual Symposium}} on {{Foundations}} of {{Computer Science}} ({{Cat}}. {{No}}.{{99CB37039}})},
author = {Frigo, M. and Leiserson, C.E. and Prokop, H. and Ramachandran, S.},
year = 1999,
pages = {285--297},
publisher = {IEEE Comput. Soc},
address = {New York City, NY, USA},
doi = {10.1109/SFFCS.1999.814600},
urldate = {2026-05-16},
isbn = {978-0-7695-0409-4}
}
@article{graefeImplementingSortingDatabase2006,
title = {Implementing Sorting in Database Systems},
author = {Graefe, Goetz},
year = 2006,
month = sep,
journal = {ACM Computing Surveys},
volume = {38},
number = {3},
pages = {10},
issn = {0360-0300, 1557-7341},
doi = {10.1145/1132960.1132964},
urldate = {2026-05-17},
abstract = {Most commercial database systems do (or should) exploit many sorting techniques that are publicly known, but not readily available in the research literature. These techniques improve both sort performance on modern computer systems and the ability to adapt gracefully to resource fluctuations in multiuser operations. This survey collects many of these techniques for easy reference by students, researchers, and product developers. It covers in-memory sorting, disk-based external sorting, and considerations that apply specifically to sorting in database systems.},
langid = {english}
}
@incollection{kaligosiHowBranchMispredictions2006,
title = {How {{Branch Mispredictions Affect Quicksort}}},
booktitle = {Algorithms -- {{ESA}} 2006},
author = {Kaligosi, Kanela and Sanders, Peter},
editor = {Hutchison, David and Kanade, Takeo and Kittler, Josef and Kleinberg, Jon M. and Mattern, Friedemann and Mitchell, John C. and Naor, Moni and Nierstrasz, Oscar and Pandu Rangan, C. and Steffen, Bernhard and Sudan, Madhu and Terzopoulos, Demetri and Tygar, Dough and Vardi, Moshe Y. and Weikum, Gerhard and Azar, Yossi and Erlebach, Thomas},
year = 2006,
volume = {4168},
pages = {780--791},
publisher = {Springer Berlin Heidelberg},
address = {Berlin, Heidelberg},
doi = {10.1007/11841036_69},
urldate = {2026-05-17},
isbn = {978-3-540-38875-3 978-3-540-38876-0}
}
@incollection{karkkainenEngineeringRadixSort2008,
title = {Engineering {{Radix Sort}} for {{Strings}}},
booktitle = {String {{Processing}} and {{Information Retrieval}}},
author = {K{\"a}rkk{\"a}inen, Juha and Rantala, Tommi},
editor = {Amir, Amihood and Turpin, Andrew and Moffat, Alistair},
year = 2008,
volume = {5280},
pages = {3--14},
publisher = {Springer Berlin Heidelberg},
address = {Berlin, Heidelberg},
doi = {10.1007/978-3-540-89097-3_3},
urldate = {2026-05-17},
isbn = {978-3-540-89096-6 978-3-540-89097-3}
}
@article{kendallStochasticProcessesOccurring1953,
title = {Stochastic {{Processes Occurring}} in the {{Theory}} of {{Queues}} and Their {{Analysis}} by the {{Method}} of the {{Imbedded Markov Chain}}},
author = {Kendall, David G.},
year = 1953,
month = sep,
journal = {The Annals of Mathematical Statistics},
volume = {24},
number = {3},
pages = {338--354},
issn = {0003-4851},
doi = {10.1214/aoms/1177728975},
urldate = {2026-05-17},
langid = {english},
file = {/home/mohammad/Zotero/storage/DSZXRR5N/Kendall - 1953 - Stochastic Processes Occurring in the Theory of Queues and their Analysis by the Method of the Imbed.pdf}
}
@article{nybergAlphasortCachesensitiveParallel1995,
title = {Alphasort: {{A}} Cache-Sensitive Parallel External Sort},
shorttitle = {Alphasort},
author = {Nyberg, Chris and Barclay, Tom and Cvetanovic, Zarka and Gray, Jim and Lomet, Dave},
year = 1995,
month = oct,
journal = {The VLDB Journal},
volume = {4},
number = {4},
pages = {603--627},
issn = {1066-8888, 0949-877X},
doi = {10.1007/BF01354877},
urldate = {2026-05-17},
copyright = {http://www.springer.com/tdm},
langid = {english}
}
@article{oneilLogstructuredMergetreeLSMtree1996,
title = {The Log-Structured Merge-Tree ({{LSM-tree}})},
author = {O'Neil, Patrick and Cheng, Edward and Gawlick, Dieter and O'Neil, Elizabeth},
year = 1996,
month = jun,
journal = {Acta Informatica},
volume = {33},
number = {4},
pages = {351--385},
issn = {0001-5903, 1432-0525},
doi = {10.1007/s002360050048},
urldate = {2026-05-17},
copyright = {http://www.springer.com/tdm},
langid = {english}
}
@incollection{sandersSuperScalarSample2004,
title = {Super {{Scalar Sample Sort}}},
booktitle = {Algorithms -- {{ESA}} 2004},
author = {Sanders, Peter and Winkel, Sebastian},
editor = {Hutchison, David and Kanade, Takeo and Kittler, Josef and Kleinberg, Jon M. and Mattern, Friedemann and Mitchell, John C. and Naor, Moni and Nierstrasz, Oscar and Pandu Rangan, C. and Steffen, Bernhard and Sudan, Madhu and Terzopoulos, Demetri and Tygar, Dough and Vardi, Moshe Y. and Weikum, Gerhard and Albers, Susanne and Radzik, Tomasz},
year = 2004,
volume = {3221},
pages = {784--796},
publisher = {Springer Berlin Heidelberg},
address = {Berlin, Heidelberg},
doi = {10.1007/978-3-540-30140-0_69},
urldate = {2026-05-17},
isbn = {978-3-540-23025-0 978-3-540-30140-0}
}
@inproceedings{satishDesigningEfficientSorting2009,
title = {Designing Efficient Sorting Algorithms for Manycore {{GPUs}}},
booktitle = {2009 {{IEEE International Symposium}} on {{Parallel}} \& {{Distributed Processing}}},
author = {Satish, Nadathur and Harris, Mark and Garland, Michael},
year = 2009,
month = may,
pages = {1--10},
publisher = {IEEE},
address = {Rome, Italy},
doi = {10.1109/IPDPS.2009.5161005},
urldate = {2026-05-17},
isbn = {978-1-4244-3751-1}
}
@article{vitterRandomSamplingReservoir1985,
title = {Random Sampling with a Reservoir},
author = {Vitter, Jeffrey S.},
year = 1985,
month = mar,
journal = {ACM Transactions on Mathematical Software},
volume = {11},
number = {1},
pages = {37--57},
issn = {0098-3500, 1557-7295},
doi = {10.1145/3147.3165},
urldate = {2026-05-17},
abstract = {We introduce fast algorithms for selecting a random sample of n records without replacement from a pool of N records, where the value of N is unknown beforehand. The main result of the paper is the design and analysis of Algorithm Z; it does the sampling in one pass using constant space and in O ( n (1 + log( N/n ))) expected time, which is optimum, up to a constant factor. Several optimizations are studied that collectively improve the speed of the naive version of the algorithm by an order of magnitude. We give an efficient Pascal-like implementation that incorporates these modifications and that is suitable for general use. Theoretical and empirical results indicate that Algorithm Z outperforms current methods by a significant margin.},
langid = {english},
file = {/home/mohammad/Zotero/storage/JZID25DZ/Vitter - 1985 - Random sampling with a reservoir.pdf}
}
@article{wulfHittingMemoryWall1995,
title = {Hitting the Memory Wall: Implications of the Obvious},
shorttitle = {Hitting the Memory Wall},
author = {Wulf, {\relax Wm}. A. and McKee, Sally A.},
year = 1995,
month = mar,
journal = {ACM SIGARCH Computer Architecture News},
volume = {23},
number = {1},
pages = {20--24},
issn = {0163-5964},
doi = {10.1145/216585.216588},
urldate = {2026-05-16},
langid = {english}
}
@inproceedings{zahariaDiscretizedStreamsFaulttolerant2013,
title = {Discretized Streams: Fault-Tolerant Streaming Computation at Scale},
shorttitle = {Discretized Streams},
booktitle = {Proceedings of the {{Twenty-Fourth ACM Symposium}} on {{Operating Systems Principles}}},
author = {Zaharia, Matei and Das, Tathagata and Li, Haoyuan and Hunter, Timothy and Shenker, Scott and Stoica, Ion},
year = 2013,
month = nov,
pages = {423--438},
publisher = {ACM},
address = {Farminton Pennsylvania},
doi = {10.1145/2517349.2522737},
urldate = {2026-05-17},
isbn = {978-1-4503-2388-8},
langid = {english},
file = {/home/mohammad/Zotero/storage/CD5FLE9Y/Zaharia et al. - 2013 - Discretized streams fault-tolerant streaming computation at scale.pdf}
}
@inproceedings{kraska2018case,
title = {The Case for Learned Index Structures},
booktitle = {Proceedings of the 2018 International Conference on Management of Data},
author = {Kraska, Tim and Beutel, Alex and Chi, Ed H. and Dean, Jeffrey and Polyzotis, Neoklis},
year = 2018,
pages = {489--504},
doi = {10.1145/3183713.3196926}
}
@article{khalifa2020learnedsort,
title = {LearnedSort: A Non-Comparison-Based Sorting Algorithm Using Neural Networks},
author = {Khalifa, Anas and others},
journal = {arXiv preprint arXiv:2003.12883},
year = 2020
}