Change random methods without losing too much performance
First of all, you should shuffle the array instead of sorting it on a random number. There can be duplicates in the random numbers, which means that lower numbers would end up earlier in the array slightly more often. This is naturally a small difference as the random numbers are large, but as you want to avoid any predictable pattern, it is still important.

Look at the Fisher-Yates algorithm for shuffling the values in an array.

To use the crypto random generator, you need a way to transform the bytes that it returns into a number in a specific range. You can use a method like the following to get a number in a range with the same probability for all numbers in the range (limited only by the randomness of the generator). It calculates the largest range of numbers that can be used to create a number in the desired range, then loops until it has picked a number in that range.

public static int GetInt(RNGCryptoServiceProvider rnd, int max) {
  byte[] r = new byte[4];
  int value;
  do {
    rnd.GetBytes(r);
    value = BitConverter.ToInt32(r, 0) &amp; Int32.MaxValue;
  } while (value &gt;= max * (Int32.MaxValue / max));
  return value % max;
}


This is based on the example on documentation page for the GetBytes method, but adapted for larger numbers.

On my computer the function will generate a million random numbers in 450 ms. The Random class does it in 20 ms, so it's slower, but not very slow. Shuffling on the other hand is faster than sorting, so you will get some performance back there.