sub Qsort # WRONG! See update below! { my $pivot = shift; # picking the pivot is usually more # involved. Afterall, you don't want # an extreme, you want both arrays to # be roughly the same size. return $pivot unless @_; my( @lt, @gt ); push( $_ gt $pivot ? @gt : @lt ) for @_; return( Qsort( @lt ), $pivot, Qsort( @gt ) ); } #### sub Qsort { my( $arrayRef, $lowIndex, $highIndex ) = @_; return undef if $highIndex le $lowIndex; my $pivotIndex = partition( $arrayRef, $lowIndex, $highIndex ); Qsort( $arrayRef, $lowIndex, $pivotIndex - 1 ); Qsort( $arrayRef, $pivotIndex + 1, $highIndex ); } # And then, of course, I need to provide &partition sub partition { my( $arrayRef, $lowIndex, $highIndex ) = @_; my $pivot = $highIndex + $lowIndex >> 1; my $pivotElement = $$arrayRef[$pivot]; while( $highIndex > $lowIndex ) { ++$lowIndex while $$arrayRef[$lowIndex] <= $pivotElement and $_[2] > $lowIndex; --$highIndex while $pivotElement <= $$arrayRef[$highIndex] and $highIndex > $_[1]; Swap( $arrayRef, $lowIndex, $highIndex ) if $highIndex > $lowIndex; } if( $highIndex > $pivot ) { Swap( $arrayRef, $pivotIndex, $highIndex ); $pivot = $highIndex; } elsif( $pivot > $lowIndex ) { Swap( $arrayRef, $pivotIndex, $lowIndex ); $pivot = $lowIndex; } return $pivot; } sub Swap { ${$_[0]}->[$_[1],$_[2]] = ${$_[0]}->[$_[1],$_[2]] } # Warning, untested code...