Student or educator? Sign up with your school email and get 6 months of Pro free.
CoChat
Sign Up
PreprintCited by 22Algorithms and Data CompressionAdvanced Combinatorial MathematicsComplexity and Algorithms in Graphs

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 access
Bacher, Axel, Bodini, Olivier, Hollender, Alexandros, Lumbroso, Jérémie·2015·arXiv
DOI 10.48550/arxiv.1508.03167arXiv 1508.03167
Open this paper in CoChat — free accountOpen PDF

Abstract

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.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

DataCite · 10.48550/arxiv.1508.03167

Cites

26 of 26 references verified0 citation errors · 0 not checkable

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.

A few free checks a day · papers already verified open instantly · results are public

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?

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

Show all 26 references

Research works printed but not linked: 1

  1. [25][25] Richard P Stanley. Catalan Numbers . Cambridge University Press, 2015. -

Cited by

Related

See all

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)
DOI
10.48550/arxiv.1508.03167
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
Licence
arxiv.org/licenses/nonexclusive-distrib/1.0/
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.