💡 104. Stooge sort in Raku

Have you ever heard of the Stooge sort algorithm? If not, it is quite interesting to learn it. The idea is clear, while you maybe need some time to see if it really works.

So, take a list of numbers and swap the first and the last elements if they are not sorted properly (that is, if the first element is bigger than the last one).

Then take the first two thirds of the data array and apply the procedure to those elements. When you are back, apply the procedure to the the right two thirds of it (thus, the two thirds but tied to the right edge). And after that, ‘confirm’ the result by stooge-sorting the first two thirds.

Repeat until everything is sorted.

This time, having some experience implementing the previous sorting algorithms, the final code is ready after the first iteration.

sub stooge-sort(@data) {
    return if [<=] @data;

    @data[0, *-1].=reverse if [>] @data[0, *-1];
    
    my $l = @data[0 ..^ Int(2/3 * ^@data)];
    my $r = @data[Int(1/3 * ^@data) .. *-1];
    
    stooge-sort($l);
    stooge-sort($r);
    stooge-sort($l);
}

my @data = 4, 5, 7, 1, 46, 78, 2, 2, 1, 9, 10;
stooge-sort @data;
say @data;

There are a few places where you can improve it a bit. The main being the check [<=] at the function entrance, which slows the whole algorithms down. One of the ideas to stop the iteration is to check if you are at the top level of recursion.

Although, I would like you to take a closer look at the fact that the function sorts data in-place, and you don’t have to pass array boundaries as function parameters.

The $l and $r variables keep the lists which refer to array slices. They are passed to another iteration level of stooge-sort, and the function changes original data. This is quite useful technique when you can pass a reference to a part of the array and modify it independently.

You can find the source file of today’s post on GitHub, feel free to share your thoughts and ideas! See you tomorrow!