The DOI matches its DataCite record; 26 of the 26 references it cites were found in a registry or an index.
MergeShuffle: A Very Fast, Parallel Random Permutation Algorithm
Open accessAbstract
This article introduces an algorithm, MergeShuffle, which is an extremely efficient algorithm to generate random permutations (or to randomly permute an existing array). It is easy to implement, runs in $n\log_2 n + O(1)$ time, is in-place, uses $n\log_2 n + Θ(n)$ random bits, and can be parallelized accross any number of processes, in a shared-memory PRAM model. Finally, our preliminary simulations using OpenMP suggest it is more efficient than the Rao-Sandelius algorithm, one of the fastest existing random permutation algorithms. We also show how it is possible to further reduce the number of random bits consumed, by introducing a second algorithm BalancedShuffle, a variant of the Rao-Sandelius algorithm which is more conservative in the way it recursively partitions arrays to be shuffled. While this algorithm is of lesser practical interest, we believe it may be of theoretical value. Our full code is available at: https://github.com/axel-bacher/mergeshuffle
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
The source backs part of the claim, not all of it — or backs it for a different population, condition or comparison.
In the citing paper
“The parallel work complexity of these recursive divide-and-conquer approaches is 𝑂 ( 𝑛 log ( 𝑛 )) .”
From Bandwidth-Optimal Random Shuffling for GPUs (2022) · cites this paper as [4]
Experimental — accuracy not yet measured
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Non-Uniform Random Variate Generation
Devroye, L. (1986) · Springer eBooks · doi:10.1007/978-1-4613-8643-8 · Cited by 4,041
OpenMP: an industry standard API for shared-memory programming
Dagum, L., & Menon, R. (1998) · IEEE Computational Science and Engineering · doi:10.1109/99.660313 · Cited by 3,343
Statistical Tables for Biological, Agricultural and Medical Research.
Reed, L. J., Fisher, R. A., & Yates, F. (1944) · Journal of the American Statistical Association · doi:10.2307/2280633 · Cited by 2,998
Bóna, M. (2015) · Chapman & Hall/CRC eBooks · doi:10.1201/b19267-16 · Cited by 2,294
Parallel programming in OpenMP
Chandra, R., Dagum, L., Kohr, D., Maydan, D. E., & McDonald, J. (2001) · Cited by 1,293
Algorithm 235: Random permutation
Durstenfeld, R. (1964) · Communications of the ACM · doi:10.1145/364520.364540 · Cited by 460
Fürlinger, J., & Hofbauer, J. (1985) · Journal of Combinatorial Theory Series A · doi:10.1016/0097-3165(85)90089-5 · Cited by 412
THE COMPLEXITY OF NONUNIFORM RANDOM NUMBER GENERATION.
Knuth, D. E., & Yao, A. C.-C. (1976) · Cited by 256
Interval algorithm for random number generation
Han, T. S., & Hoshi, М. (1997) · IEEE Transactions on Information Theory · doi:10.1109/18.556116 · Cited by 141
Un procédé itératif de dénombrement d'arbres binaires et son application à leur génération aléatoire
Rémy, J.-L. (1985) · RAIRO Informatique théorique · doi:10.1051/ita/1985190201791 · Cited by 114
Fast parallel generation of random permutations
Hagerup, T. (1991) · Lecture notes in computer science · doi:10.1007/3-540-54233-7_151 · Cited by 66
Random permutations on distributed, external and hierarchical memory
Sanders, P. (1998) · Information Processing Letters · doi:10.1016/s0020-0190(98)00127-6 · Cited by 66
Parallel algorithms for generating random permutations on a shared memory machine
Anderson, R. (1990) · ACM Symposium on Parallelism in Algorithms and Architectures (SPAA) · doi:10.1145/97444.97674 · Cited by 49
Optimal Discrete Uniform Generation from Coin Flips, and ApplicationsPreprint
Lumbroso, J. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1304.1916 · Cited by 43
Self-citationFast Generation of Random Permutations Via Networks Simulation
Czumaj, A., Kanarek, P., Kutyłowski, M., & Loryś, K. (1998) · Algorithmica · doi:10.1007/pl00009206 · Cited by 40
A parallel algorithm for the generation of a permutation and applications
Alonso, L., & Schott, R. (1996) · Theoretical Computer Science · doi:10.1016/0304-3975(95)00198-0 · Cited by 31
Randomized permutations in a coarse grained parallel environment
Gustedt, J. (2003) · ACM Symposium on Parallelism in Algorithms and Architectures (SPAA) · doi:10.1145/777412.777454 · Cited by 29
Engineering Parallel In-Place Random Generation of Integer Permutations
Gustedt, J. (2008) · Springer eBooks · doi:10.1007/978-3-540-68552-4_10 · Cited by 28
Sequential Random Permutation, List Contraction and Tree Contraction are Highly Parallel
Shun, J., Gu, Y., Blelloch, G. E., Fineman, J. T., & Gibbons, P. B. (2015) · Cited by 24
Efficient random sampling of binary and unary-binary trees via holonomic equations
Bacher, A., Bodini, O., & Jacquot, A. (2017) · Theoretical Computer Science · doi:10.1016/j.tcs.2017.07.009 · Cited by 19
Self-citationOn Buffon Machines and Numbers
Flajolet, P., Pelletier, M., & Soria, M. (2011) · ACM-SIAM Symposium on Discrete Algorithms (SODA) · doi:10.1137/1.9781611973082.15 · Cited by 19
(1961) · Cited by 19
A Simple Randomization Procedure
Sandelius, M. (1962) · Journal of the Royal Statistical Society Series B: Statistical Methodology · doi:10.1111/j.2517-6161.1962.tb00474.x · Cited by 13
An Empirical Analysis of Parallel Random Permutation Algorithms on SMPs
Cong, G., & Bader, D. A. (2006) · SMARTech Repository (Georgia Institute of Technology) · Cited by 12
Sampling with arbitrary precision.Preprint
Devroye, L., & Gravel, C. (2015) · arXiv (Cornell University) · Cited by 7
Devroye, L., & Gravel, C. (2015) · arXiv (Cornell University) · doi:10.48550/arxiv.1502.02539 · Cited by 3
Research works printed but not linked: 1
- [25][25] Richard P Stanley. Catalan Numbers . Cambridge University Press, 2015. -
Cited by
Scalable generation of graphs for benchmarking HPC community-detection algorithms
Slota, G. M., Berry, J. W., Hammond, S. D., Olivier, S. L., Phillips, C. A., & Rajamanickam, S. (2019) · International Conference for High Performance Computing, Networking, Storage and Analysis (SC) · doi:10.1145/3295500.3356206 · Cited by 29
Secure and Efficient Compressed Sensing-Based Encryption With Sparse Matrices
Cho, W., & Yu, N. Y. (2019) · IEEE Transactions on Information Forensics and Security · doi:10.1109/tifs.2019.2953383 · Cited by 25
Probabilistic Concurrent Reasoning in Outcome Logic: Independence, Conditioning, and Invariants
Zilberstein, N., Silva, A., & Tassarotti, J. (2026) · Proceedings of the ACM on Programming Languages · doi:10.1145/3776651 · Cited by 19
Bandwidth-Optimal Random Shuffling for GPUs
Mitchell, R., Stokes, D., Frank, E., & Holmes, G. (2022) · ACM Transactions on Parallel Computing · doi:10.1145/3505287 · Cited by 6
Parallel Generation of Simple Null Graph Models
Garbus, J., Brissette, C., & Slota, G. M. (2020) · IEEE International Symposium on Parallel & Distributed Processing, Workshops and Phd Forum · doi:10.1109/ipdpsw50202.2020.00181 · Cited by 6
Metadata
- Authors
- Bacher, A., Bodini, O., Hollender, A., & Lumbroso, J.
- Affiliations
- TU Wien (AT)
- Université Sorbonne Paris Nord (FR)
- ORCID
- Bodini, Olivier
- Venue
- arXiv
- Publisher
- arXiv
- Published
- 2015
- ISSN
- 2331-8422 (ISSN-L)
- arXiv
- 1508.03167
- OpenAlex
- W1905750377
- Cited by
- 18
- References
- 26
- Citations by year
- 2026: 2 · 2025: 3 · 2024: 4 · 2023: 3 · 2022: 1 · 2021: 1 · 2020: 1 · 2019: 3
- Type
- posted content
- Language
- en
- Open access
- green
- arxiv.org
- Locations
- arXiv (Cornell University) (submittedVersion)
- arXiv (Cornell University)
- Funders
- Agence Nationale de la Recherche (ANR-23-CE48-0014)
- Austrian Science Fund
- Topics
- Physical Sciences › Mathematics › Theoretical Computer Science › Algorithms and Data Compression
- Physical Sciences › Mathematics › Discrete Mathematics and Combinatorics › Advanced Combinatorial Mathematics
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Complexity and Algorithms in Graphs
- Keywords
- increasing trees, PRAM, OpenMP
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.
