There is no way to use the perl's built-in sort to achieve your goal.

If your storing 32-bit integers in a string, then you effectively have a C-style array of ints. It would therefore be fairly easy (assuming that you compile your own perl) to use Inline::C to get at the base address of that C-style array, ie. the base address of the scalar, and use your C-RTL's qsort() routine to do the sorting. This would be far quicker than any Perl solution.

If you use a binary distribution of perl, then it would still be possible, though awkward, to use the C-RTL qsort(). Getting the base address of the scalar can be done with pack, and (assuming AS perl), it should be possible to use Win32::API to get the entrypoint for qsort(). The problem then would be providing a callback address for the comparison function. Possibly possible :), but awkward and fragile. Mapping the pointers the qsort function gives to the compare function from one string to valid pointers into another would be possible, but messy.

I had a play with implementing a pure perl qsort using vec to get at the individual integers. It works, and could be used to sort one string based upon the contents of another (although I'm not entirely sure I understand what you mean by that), but it wouldn't be quick by any stretch of the imagination.

I tried it on 100,000 ints and it took a little under 5 minutes, which is an order of magnitude slower than using sort on a standard array. For contrast, the C-RTL qsort() function will do 1,000,000 in 4 seconds. I'm afraid that this is one of those things that there is simply no substitute for getting closer to the metal and using C or assember.

How do you do a perl quicksort ?

If you just want to use the quicksort algorithm on a standard perl array, then prior to (I think) 5.8.0, perl's built-in sort used that algorithm. From 5.8.0 on, you have to request the quicksort algorithm be used in preference to the now default mergesort using the sort pragma

use sort qw[ _quicksort ];
[download]

In the case of the post to which you refer, the OP was looking to save space by storing integers in a packed (or veced) scalar. As the built-in sort doesn't know how to deal with these, it becomes necessary to implement the qsort algorithm yourself. This is the code I knocked up back then to test the performance of a pure perl implementation using vec.

#! perl -slw
use strict;
use Benchmark qw[ timethis ];

local $, = ' ';

our $SIZE ||= 4; our $N ||= 100; $N--;

sub qSortVec {
    my( $rVec, $size, $left, $right ) = @_;

    if( $left < $right ) {
        my( $u, $d ) = ( $left, $right );
        my $pivot = vec( $$rVec, ( $u  + $d  ) / 2, $size );
        do {
            $u++ while ( vec( $$rVec, $u,  $size ) < $pivot );
            $d-- while ( vec( $$rVec, $d,  $size ) > $pivot );

            if( $u <= $d  ) {
                my $temp                  = vec( $$rVec, $u,  $size );
                vec( $$rVec, $u,  $size ) = vec( $$rVec, $d,  $size );
                vec( $$rVec, $d,  $size ) = $temp;
                $u++; $d--;
            }
        } while $u  <= $d;

        qSortVec ( $rVec, $size, $left,  $d  );
        qSortVec ( $rVec, $size, $u,  $right );
    }
}

srand( 1 );
our $vec ='';
vec( $vec, $_, $SIZE ) = int rand( 1 << $SIZE ) for 0 .. $N;

print map{ vec( $vec, $_, $SIZE ) } 0 .. $N;

our $copy;
timethis( 10, q[ $copy = $vec; qSortVec( \$copy , $SIZE, 0, $N ) ] );

print split"(.{$SIZE})", unpack 'B*', $vec;
print map{ vec( $copy, $_, $SIZE ) } 0 .. $N;

my $res = 0; 
$res  |= vec( $copy, $_, $SIZE ) > vec( $copy, $_+1, $SIZE ) for 0 .. 
+$N-1;

print 'Sort error' if $res;
[download]

---

Examine what is said, not who speaks.

"Efficiency is intelligent laziness." -David Dunham
"Think for yourself!" - Abigail