Problems? Is your data what you think it is?  
PerlMonks 
Re: RFC: Sorting IPv4 addressesby ELISHEVA (Prior) 
on Oct 07, 2009 at 18:54 UTC ( [id://799781] : note . print w/replies, xml )  Need Help?? 
Note:The version of the test I used includes split_pack, but not Sort::Key::IPv4 or Sort::Key::Radix and fixes a small typo in naive_sort (my @b = split /\./, $a; should be my @b = split /\./, $b;) Still, this makes me wonder about the Schwartian transform. The argument for it is that during a naive sort we are likely to need to extract the sort key several times. The cumulative time for the repeat derivation of the sort key is more than the extra work of reconstructing the original value from the sort key and the extra copying and memory allocation needed by the three step process. Hence the Schwartzian transform is faster. But is this always true? It would seem to depend on four factors:
Perl sort uses quicksort. If the array is completely ordered,then each sort key (other than the first and last) will be derived twice  once to compare N1 to N and once to compare N to N+1. In the average case 2N becomes 2N*logN and only in the worst case it is 2*N^2. Putting this all together, the Schwartzian transform is only faster if N*(extract_sortkey + reconstruct_value + 2*memcopy) < extract_sortKey*N*X where X is 2 in the best case, log N on average and N in the worst case. This simplifies to reconstruct_value + 2*memcopy < extract_sortkey*(X  1). Thus we have:
Note that the Schwartian side is a constant and the naive side scales with respect to N. Surely a process that scales by N will be slower than a constant process? Not necessarily. The problem here is that we are comparing apples and oranges. On one side of the equation is "reconstruct_key + 2*memcopy" and on the other is "extract key". These are very different operations and we may be comparing very slow operations to very fast operations. For instance, if the process of reconstructing the original value is 10X slower than extracting the key, we would need to be sorting a fairly large array of N=1024=2^10 values before the Schwartzian transfom would give us any speed advantage. The moral of this story is that there is no automatically right way to sort  it all depends on the size of your data set, the likelihood that it will be badly ordered, and the difference between the time involved in extracting sort keys and the time needed to reconstruct original values. Best, beth Update:Fixed who "wins"  misunderstood output! Thanks to bv, ikegami below.
In Section
Meditations
