General Sort Routines

This library includes general purpose sorting routines which are tuned on daware. That doesn't mean they aren't fast for general sorting just that we test them with daware.

General Sorting Routines

• sort::inplace::quick() should be used for slow value access (e.g. sorting pointers)
  • It uses three pivot quicksort to reduce the number of value accesses and comparisons
• sort::copy::quick() should be used for slow value access (e.g. sorting pointers) if additional space may be used
  • It copies key and value together before sorting to improve speed
• sort::inplace::block() should be used for fast value access (e.g. sorting integers)
  • It is optimized to reduce the number of branch misses

Common Interface for General Sorting Routines

• [first, last) is the iterator range to be sorting
• optional: [Sf, Sl) is the additional space to use for copy
  • should be iterators to std::pairs able to hold a key and a value
• index is a callback which returns to value for a key
  • This allows to optimize the number of dereferences better than a comparsion function
  • For integer data this is just a simple identity
  • For structs one can use std::tie to define the sorting order
  • Worst case means having to override the comparsion operators of the returned type
• cb is a callback which gets called on equal ranges
  • For each unique value a call cb(first, last) happens
  • The rest of the range is NOT guaranteed to be already sorted when called
  • It IS guaranteed that all elements with this value are within the called range
• <LR> is a template argument defining the order in which we sort
  • defines if we call cb from the lowest to the highest value (Left to Right) or otherwise
  • NOCB defines not to call the cb at all (this saves some overhead compared to an empty cb)