How to randomly sort an array

In this article, I will introduce a random sort algorithm with a complexity of O(n).

A randomized array is widely used in games (e.g., Poker) and other systems alike. So I assume it is a commonly encountered program difficulty.

The most intuitive approach is slow. To randomly sort elements in an array A and copy the results to B, this approach 1) uses a random generated number as an; 2) fetch the element from array A using the index; 3) checks if the element exists in B already; 4) if not, insert the element in B and 5) If so, goes back to 1) and regenerates a random index again and conducts the check. As the program proceeds and the B grows bigger, it is more likely that a randomly selected element already exists in B, so the algorithm has to redo everything again (regenerate an index, iterate B to check if the element exists) from 5). When the program reaches the very end of the procedure, the performance becomes unacceptably slow.
To avoid the collision, we can remove the element from A once it is selected. The art is about how to remove to achieve O(n):

1) each time we select an element we append it in the new array;
2) we assign the element from the original array with the last element in the tail;
3) we reduce the size of the original array by 1.

And here is the code: