Rao-Sandelius Shuffle

The Rao-Sandelius shuffle is a divide-and-conquer algorithm for randomly shuffling a finite sequence, described by C. Radhakrishna Rao in 1961 and refined for efficiency by Martin Sandelius in 1962. Each element is assigned a random value, the sequence is partitioned into subsequences according to those values, and each subsequence is then shuffled recursively in the same way. Although it uses more swaps than the Fisher-Yates shuffle for the same input, its memory access pattern has better cache locality and is easier to parallelize, so for very large sequences, such as around a billion items, it can outperform Fisher-Yates in practice. This description is adapted from Wikipedia contributors under CC BY-SA 4.0; changes were made. https://creativecommons.org/licenses/by-sa/4.0/