My Project
|
stxxl::sort is an external memory equivalent to STL std::sort. The design and implementation of the algorithm is described in detail in [DemSan03].
ExtIterator
is a model of External Random Access Iterator (In STXXL currently only stxxl::vector provides iterators that are models of External Random Access Iterator.).ExtIterator
is mutable.StrictWeakOrdering
is a model of StrictWeakOrdering Comparison ConceptExtIterator's
value type is convertible to StrictWeakOrdering's
argument type.Model of StrictWeakOrdering Comparison concept must:
min_value()
and max_value()
can not be present in the input sequence.A comparator class for integers: my_less_int.
A comparator class my_less, that could be instantiated as e.g. my_less<int>
, my_less<unsigned long>
, etc.
[first, last) is a valid range.
stxxl::sort chooses the block size (parameter B) equal to the block size of the container, the last and first iterators pointing to (e.g. stxxl::vector's block size).
The second term in the I/O complexity accounts for the merge phases of the external memory sorting algorithm [DemSan03]. Avoiding multiple merge phases speeds up the sorting. In practice one should choose the block size B$of the container to be sorted such that there is only one merge phase needed: . This is possible for
and
. But still this restriction gives a freedom to choose a variety of blocks sizes. The study [DemSan03] has shown that optimal B for sorting lies in the range
. With such choice of the parameters the stxxl::sort always performs
I/Os.
The stxxl::sort consumes slightly more than M bytes of internal memory.
The stxxl::sort is not in-place. It requires about N bytes of external memory to store the sorted runs during the sorting process [DemSan03]. After the sorting this memory is freed.
STXXL gives an ability to automatically check the order in the output of STXXL sorters and intermediate results of sorting (the order and a meta information in the sorted runs). The check is switched on if the source codes and the library are compiled with the option -DSTXXL_CHECK_ORDER_IN_SORTS
and the option -DNDEBUG
is not used. For details see the compiler.make
file in the STXXL tar ball. Note, that the checking routines require more internal work as well as additional I/Os to read the sorted runs. Therefore for the final non-debug version of a user application on should switch this option off.
This checker checks the stxxl::sort, stxxl::ksort, and the pipelined sorter.