If you add print "@_"; to the top of your sub, you'll see the problem.

Even when @less, @great and $pivot are empty, you still recurse.

Changing your first line to: my $pivot=pop // return; will allow the recursion to terminate.

how does the // part work?

JediMasterT,
See perlop. The // operator essentially is a special or operator where it is testing the left hand side for definedness. I am pretty sure this became available in perl 5.10 four years ago but you can check perlhist and perldelta if you want to be sure.

Cheers - L~R

If the left part is not defined, the right is returned, otherwise the left one is. See perlop.

@end = quicksort(3, 2, 6, 5, 4);
foreach (@end) {
    print "$_ ";
}
print "\n";

sub quicksort {
    @arr=@_;
    if($#arr < 1)
    {
          return @arr;
    }
    my $pivot=pop(@arr);
    my @less; my @great;
    foreach (@arr) {
       # print "@_";
        if ($_<$pivot) {
            push @less,  $_;
        } else {
            push @great, $_;
        }
    }
    return quicksort(@less), $pivot, quicksort(@great);
}
[download]

Unrelated to your sort, you might like this:

#foreach (@end) {
#    print "$_ ";
#}
#print "\n";

print "@end\n";
[download]

Yeah, I've been programming in Java for school, so I forgot how the print function works. I found out today, and was wondering how long it would take for someone to point it out.

Woke up this morning and realized I didn't have a terminating return @_ if (@#_<1); Derp. Thanks for all the replies, though.

#!/usr/bin/perl -slw

use strict;
use warnings;
use Tie::Quicksort::Lazy TRIVIAL => 2;

my @end = qw/ 3 2 6 5 4 /;
my @sorted_input = sort @end;

tie my @sorted, 'Tie::Quicksort::Lazy', @end;
while (@sorted) {
    my $this = shift @sorted;
    print $this;
}
[download]

I recommend that you use Perl sort() rather than trying to implement a my_sort() routine yourself.

Update: I skipped Perl 5.8 and went straight from 5.6 to 5.10. I know that the worst case quicksort issue (already ordered) went away. But more happened than just that. The sorting got significantly faster. Probably a combination of algorithm and implementation changes? I have not investigated all of the details. I just know that it is a lot faster. The sort time got so much better that it has caused me to re-think many places where I used techniques like Schwartzian transform.

As a learning exercise, I think one should be familiar with all the basic sorting algorithms. There is a lot to be learned from that and there is a reason why this is taught in every CS curriculum. I guess I just wound up with a very long winded way of saying: the Perl sort() function is no slouch!

While this is usually true in Perl, learning how different sorts work, how to implement them yourself, bigOh analysis of them, and under what scenarios they should or should not be used have great value.

When in college, we had two schools teaching "computer science" - the CS program under the sciences, and one of the business tracks under the school of business. The school of business basically taught the students to use the foo function of the language de jour to do action bar. I helped a few people in my circle of influence from the business school wow their instructors (How's that so fast?) and classes by teaching them some of those differences. I also took on some projects speeding up code submitted by other (Update: I was in CS, not Business) business students as projects for departments around campus.

My point is that even if the language's sort is the best for the purpose, it does not hurt to learn other methods, nor is it bad to know why it is the best for the purpose. Trying to implement it oneself can also give insight as to why the language's sort is the better choice.

--MidLifeXis

Interestingly enough, up until 5.8, Perl used Quicksort for sort()