Re: questions about the STL sort()
Hello,
feverzsj wrote:
STL sort() as an implementation of introsort, below is the code
snippet from the gnu stl.
my question is : why not use two recursive calls to __introsort_loop,
it will have a clear view to present a divide-and-conquer algorithm.
Yes, it is a optimization,but tail recursion elimination is now a
common technique of today's cpp compiler.
I'm not sure tail recursion does apply here. Since the code is there,
you could try out what the compilers do. I'm pretty sure that saving
one recursive call saves enough, e.g. initializing the iterators for
every recursive instance, to justify doing it that way. Automatically
transforming non-tail recursion away, even partially, is a pretty
complicated operation with too many problematic cases. I would not
expect any compiler sacrificing lots of time in fruitless analysis in
that area.
another question is about the __final_insertion_sort() placed after
the call to __introsort_loop()
below is the code snippet.
template<typename _RandomAccessIterator>
void
__final_insertion_sort(_RandomAccessIterator __first,
_RandomAccessIterator __last)
{
if (__last - __first > _S_threshold)
{
std::__insertion_sort(__first, __first + _S_threshold);
std::__unguarded_insertion_sort(__first + _S_threshold, __last);
}
else
std::__insertion_sort(__first, __last);
}
why not just call one __insertion_sort in the if-condition?
__unguarded_insertion_sort saves bounds-checking, therefore it needs
some elements less or equal in the area before first + _S_threshold. It
will always read at least at position __first + _S_threshold - 1, and
it will sort arbitrarily far before __first + _S_threshold. The big
question is, why there must be an element less then all in range
[__first + _S_threshold, __last) in the range [__first, __first +
_S_threshold). An that can only be found when looking at the places
calling this function.
I think this splitting should make an easily measurable difference when
sorting containers of small elements like integer.
Bernd Strieder