Everytime someone posts a question about bubble sorts, someone else points out that bubble sorts are "the worst sorting algorithm possible", being O(n^2).

Of course, we can do much worst than O(n^2). I present here a much better candidate for "the worst", the splatter sort, which will take on average O(n!). (Well, O(m!), where m is the number of distinct values among the n elements.)

This algorithm was inspired by many student assignments back when I was a corrector in university, where the student would do

while(list_isnt_sorted()) {
  do_buggy_transform();
}

and claim their code was right because it eventually terminated with a sorted list...

A more advanced version would use a code ref to pass to is_sorted, so we could have different sort criteria like perl's sort routine does...

Just when you thought sorts couldn't get any worst :)

(Edit: D'oh! This isn't as bad as it could be. Since I check if the list is sorted before shuffling, this will unfortunately do quite well on already sorted data. Pessimizing the code further isn't too challenging an exercise, though :) )

# 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;
}
[download]