Possibly use the inside-out shuffle

[chrisdone]

The Mutable sort is the modern in-place Fisher-Yates sort, which is great.

I noticed that the Immutable version does a copy of the memory and then re-uses Fisher-Yates.

Another option for the immutable version is the Inside out algorithm, in which you'd simply allocate an unitialized mutable vector at the given size, and then do O(n) updates to it, then do an unsafeFreeze. This way you avoid the O(n) copy of the immutable original array.

I haven't actually done any benchmarks. But I was randomly perusing shuffling algos and thought of this package. 🙂