Shuffling algorithms

Shuffling is equivalent to generating a random permutation of a given array.

Knuth's shuffling algorithms:

1. Simple Shuffle:
Assign a random number to each card, and then sort the cards in order of their random numbers. This will generate a random permutation, unless two of the random numbers generated are the same. This can be eliminated either by retrying these cases, or reduced to an arbitrarily low probability by choosing a sufficiently wide range of random number choices.
Complexity: O(n log n) because of sorting (using mergesort or heapsort, etc.)

2. Knuth shuffle or Fisher-Yates shuffle:
Move through the array from top to bottom (i.e, index 0,1,..,n), swapping each card in turn with another card from a random position in the part of the pack that has not yet been passed through (including itself). With unbiased random numbers, it always generates a random permutation.
Complexity: O(n)

/** Generates a random permutation of the array using Knuth's shuffle algorithm */
public static void knuthShuffle(int[] a) {
  for (int i = 0; i < a.length; i++) {
    // Pick a random index in i ... a.length-1
    int k = i + (int) (Math.random() * (a.length - i));
    // Swap.
    int temp = a[i];
    a[i] = a[k];
    a[k] = temp;
  }
}

---