Move Random into Base?

“Better algorithm” is a tricky thing to define

Agreed, but I think in the context of a standard library it’s clear that it’s preferable for a sorting algorithm of optimal asymptotic complexity in the worst case to be available, because the standard library needs to provide users with functionality that’s generally useful.
As opposed with code optimized for special cases (“no adversarial input” is an example), which is less essential for a standard library to have.

If this is a high priority for you, you’re always welcome to submit a pull request!