[Tim]
>> 1. Merge "2 at a time" instead of just 1. That is, first "sort" the
>> next 2 elements to be merged (1 compare and a possible swap). Then
>> binary search to find where the smaller belongs, and a shorter binary
>> search to find where the larger belongs. Then shift both into place.
[Armin]
> Good idea, but when I tried that it seemed to increase the total
> number of comparisons (on random inputs with only up to 136 items).
> The increase is on the order of 5%. I'm not sure reduced data
> movement can compensate for that in Python.
Which is another way of saying "bad idea" - that must be why I didn't
pursue it to begin with ;-)
Thanks for trying! I plugged a similar routine into the code I showed
before to count the # of comparisons in Nha Pham's idea, and this
"merge 2 at a time" thing has a higher average # of compares (over all
permutations) than Nha's (which in turn has a higher average than the
status quo).
That makes some sense, thinking about what they do. Nha's algorithm
has some supernaturally good cases (input array already ascending or
already descending), but "merge 2 at a time" doesn't appear to have
any.
In any case, the information-theoretic minimum average number of
comparisons for merging N sorted elements with 2 sorted elements is
("where do the 2 belong in the final list of N+2 elements?" =
comb(N+2, 2)):
log2((N+2)*(N+1)/2) = log2(N+2) + log2(N+1) - 1
Add a comparison to get the 2 elements in order to begin with, and we're up to
log2(N+2) + log2(N+1)
Two independent binary inserts (first to a list of size N, and then to
a list of size N+1) comes out to the same. So even being
supernaturally clever can't reduce the average number of compares this
way. And since, in context, we're only looking at short arrays, a
marginal saving in data movement costs (which are still O(N**2) worst
case) are unlikely to be significant.
Still, if anyone wants to go nuts ... ;-)
_______________________________________________
Python-Dev mailing list
Python-Dev@python.org
https://mail.python.org/mailman/listinfo/python-dev
Unsubscribe:
https://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
