Unbiased Shuffle Algorithm

I have recently been fascinated by the mathematics of shuffling, or randomly reassigning values to different indices within an array of elements. Wikipedia has a good article about the Fisher-Yates shuffle, which, “properly implemented, … is unbiased, so that every permutation is equally likely.” Here is a C# implementation of the Fisher-Yates shuffle that runs in linear, or O(n), time:

private void Shuffle (ref string[] values)
{
  Random rand = new Random(); // used to generate random positive integers
  int n = values.Length;      // length of the array
  int r = 0;                  // swap index
  string swap = String.Empty; // copy of string to swap

  // iterate through each item in the array
  for (int i = 0; i < n; i++)
  {
    // get random index of an item to swap with the current item
    r = i + rand.Next(n - i);

    // swap items
    swap = values[r];
    values[r] = values[i];
    values[i] = swap;
  }
}

You’ll notice that I’m sending in the array of strings as a reference argument instead of making a copy of the array and returning a new shuffled copy as the return type (which would be extremely inefficient).