Details
-
Improvement
-
Status: Resolved
-
Blocker
-
Resolution: Fixed
-
None
-
None
-
None
Description
The only sort routine you can count on the system providing is qsort. Some
systems provide a qsort_r which takes a context argument in addition to the
items being compared, but not all, and the function signature differs on the
systems that do provide it (with context being either the first or the last
argument to the comparison function).
Lucy::Util::SortUtils provides a context-aware quicksort and a context-aware
mergesort. The mergesort also exposes merge routines which are optimized for
use by an external sorter, as they minimize copying.
The quicksort implementation guards against the classic quicksort worst-case
behavior with careful pivot selection. One popular quicksort optimization is
still TODO: using insertion sort for array slices of 10 or fewer elements.
Implementing that optimization may be worthwhile, as this quicksort will
probably be used for the first level of token-sorting at index time.