ANN: blist 1.2.0

[Terry Reedy]

On 7/21/2010 12:15 PM, Daniel Stutzbach wrote:

> Here's a performance comparison of sorting with blist versus 3.1's list:
> http://stutzbachenterprises.com/performance-blist/sort-random-list

Question related to possible addition of radix sort to lists:

These tests use random numbers with a constant, relatively high density 
of 25%, which is favorable to radix sort. What if you do the same test 
with a constant range of, say, 1000000000 (1 billion) or even a trillion 
or quadrillion. Or how about sorting a thousand 128bit ip6 addresses? 
Which wins for that?

list.sort is (near) linear for lists that are mostly ordered. I think 
Tim's writeup about this in in the source. For instance, if one extends 
a sorted with 1% random additions and resorts, list.sort will skip the 
sorted part, sort the additions, and merge them back in. Radix sort 
ignores pre-existing order. So either a lot of comparitive profiling 
would be needed for auto-selection of sort method, or it should be user 
selectable.

Does your radix sort meet the stability guarantee of list.sort?
If not, a separate .rsort method would be needed anyway.

-- 
Terry Jan Reedy