Descending numeric sort using Guttman-Rosler Transform

[Andrew Savige]

The following program is a simple example of sorting positive integers
using the Guttman-Rosler transform:

print map { substr($_, 4) } sort map { pack('N', $_) . $_ } <DATA>;
__END__
2
256
255
32000
33000
12345678
12345679
1234567
1

It seems to me that pack('N', $_) is sound while pack('L', $_) is
unsound (because 'N' is guaranteed big-endian, while 'L' is not).
Is that right?

What is the recommended way to do a descending numeric sort?
Changing pack('N', $_) to pack('N', -$_) seems to work.
Is it sound?

If the data contains negative integers, the simple program above
does not work. What is the recommended technique in that case?
Changing pack('N', $_) to pack('N', $_ ^ (1 << 31)) seems to work.
Is it sound?

/-\

 

[Tassilo v. Parseval]

Also sprach Andrew Savige:

The following program is a simple example of sorting positive integers
using the Guttman-Rosler transform:

print map { substr($_, 4) } sort map { pack('N', $_) . $_ } <DATA>;
__END__
2
256
255
32000
33000
12345678
12345679
1234567
1

It seems to me that pack('N', $_) is sound while pack('L', $_) is
unsound (because 'N' is guaranteed big-endian, while 'L' is not).
Is that right?

Right. 'L' is the native byte-order so it will only yield correct
results on big-endian machines. Well, I mean you could also do a

map { (reverse pack "V", $_) . $_ } <DATA>

;-)

What is the recommended way to do a descending numeric sort?
Changing pack('N', $_) to pack('N', -$_) seems to work.
Is it sound?
Yes.

If the data contains negative integers, the simple program above
does not work. What is the recommended technique in that case?
Changing pack('N', $_) to pack('N', $_ ^ (1 << 31)) seems to work.
Is it sound?

No:

print -2147483646 ^ (1<<31);
print "\n";
print 2147483650 ^ (1<<31);
__END__
2
2

And suddenly a negative and a positive number become equal. So you are
limited by the number of bits your perl was compiled for. It may work
for perls compiled with 'use64bitall=define'. But at some point you
always have the problem that the numbers will get too large.

However, for a simple numeric sort (either descending or default order),
the Guttman-Rosler transform is not the right tool since

sort { $a <=> $b } @list;
sort { $b <=> $a } @list;

are special cases that have been optimized in the perl core. So the
above two will give significantly better performance than any transform.

Tassilo