The Schwartzian Transform is useful primarily because of its scalability - when sorting, the number of calls to the comparator is somewhere between O(nlogn) and O(n2) [0], so if some of the effort can be offloaded to an O(n) comparison you would normally except it to be a win at some point as the array to be sorted grows.
(Note though that this is not guaranteed, since the cost of the extra memory used by the ST does not grow linearly.)
The GRT [1] has the added benefit that we end up using one of perl's built-in sort comparators (the simple $a cmp $b or $a <=> $b), which means that the entire sort is run directly in C code without resorting to the perl interpreter for each comparison.
To my mind, there are only three reasons why you might not want to use one of these transforms on any sort in your program: if you are sorting a list of (small and) bounded size; if you are likely to be in a limited memory situation such that the transforms might cause you either to run out of memory or start swapping; or (and I think this is the most common case) if the added code complexity outweighs the likely speed advantages - never forget the high resource cost of code maintenance.
Hugo
[0] see An informal introduction to O(N) notation
[1] see Resorting to Sorting for a tutorial on these and other sorting techniques
|