# stolen from sauoq, who attributed it to perdoc -q shuffle:
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];
    }
}

sub is_sorted {
    my $list_r = shift;
    my $prev=$list_r->[0];

    for(my $i=1;$i<scalar @$list_r;++$i) {
        return 0 if $list_r->[$i]<$prev;
        $prev=$list_r->[$i];
    }

    return 1;
}

# sort list passed by reference in place, returning 
# reference to sorted list
#
# takes n! time.

sub splatter_sort {
    my $list_r=shift;

    while(!is_sorted($list_r)) {
        fisher_yates_shuffle($list_r);
    }

    return $list_r;
}