Skip to content

Instantly share code, notes, and snippets.

@danlark1
Created Apr 19, 2022
Embed
What would you like to do?
void
__introsort(_RandomAccessIterator __first, _RandomAccessIterator __last,
difference_type __depth) {
// ...
while (true) {
if (__depth == 0) {
// Fallback to heap sort as Introsort suggests.
_VSTD::__partial_sort<_Compare>(__first, __last, __last);
return;
}
--__depth;
// ...
}
template <typename _Number>
inline _Number __log2i(_Number __n) {
_Number __log2 = 0;
while (__n > 1) {
__log2++;
__n >>= 1;
}
return __log2;
}
void __sort(_RandomAccessIterator __first, _RandomAccessIterator __last) {
difference_type __depth_limit = 2 * __log2i(__last - __first);
_VSTD::__introsort(__first, __last, __depth_limit);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment