| Jeff Reid 2007-10-20, 3:57 am |
| > C++'s sort()
A "natural" merge sort is faster than C++'s sort() for most cases.
The main exception is when the default comparator can be used instead of
a user comparator, and if the compare time is about the same as the swap
time (or less). When sorting an array of 64 bit random numbers in 64 bit
mode, the C++ sort() was about 17% faster than the merge sort. However,
if the record size is large enough to justify sorting pointers instead of
the data directly, then the merge sort was much faster. The C++ sort()
typically has over 50% more compares than a merge sort for random data.
If there's any significant ordering within a set of elements, a natural
merge sort is much faster than sort(). In the case of a pre-sorted file,
a natural merge sort does N-1 compares, no data movement and it's done.
|