The following is straight out of the FAQ. Use perldoc -q shuffle to read the whole entry.

sub fisher_yates_shuffle {
    my $deck = shift;  # $deck is a reference to an array
    my $i = @$deck;
    while ($i--) {
        my $j = int rand ($i+1);
        @$deck[$i,$j] = @$deck[$j,$i];
    }
}
[download]

Update: Uh. Gee... you did ask for the theory not the code. Sorry. What is there to tell you? It's O(N) for obvious reasons and it works on the data in place so memory usage is minimal. It's a very straightforward algorithm.

-sauoq
"My two cents aren't worth a dime.";