Re: [boost] Proposed templated integer_sort

From: Phil Endecott (spam_from_boost_dev_at_[hidden])
Date: 2008-07-12 11:48:09

Steven Ross wrote:
> Are there any more suggestions for the core algorithm?

Log2 can be done in O(log Nbits) steps, rather than O(Nbits).

I spent a while trying to understand this bit of code:

//Swap into place
//This dominates runtime, especially in the swap; std::sort calls are 
the other main time-user
RandomAccessIter current = first;
for(unsigned u = 0; current != last; ++u) {
        for(current_bin = (bins + ((*current >> log_divisor) - div_min));  
(current_bin->count > u);
                current_bin = bins + ((*current >> log_divisor) - div_min))
                        std::swap(*current, *(current_bin->current_position++));
        //Now that we've found the item belonging in this position, increment 
the bucket count
        if(current_bin->current_position == current++)
                ++(current_bin->current_position);
}

You don't help understanding by changing the meaning of bin.count half 
way through :-(.  Anyway, I think you're doing more work than necessary 
here.  For each bin, the elements between the start of the bin and 
bin.current_position will be correct and can be skipped over; this will 
be on average half of the elements.  This doesn't save any swaps but it 
does save the shifting and some comparisons.  Pseudo-code:

for each bin {
   for each element between this bin's current_position and its end {
     while (1) {
       determine the bin this element should be in
       if it's in the right bin { break }
       else {
         swap it with the element at the right bin's current_position
         increment that bin's current_position
       }
     }
   }
}

Have I understood this correctly?

Phil.