79301749

Date: 2024-12-22 21:21:54
Score: 0.5
Natty:
Report link

std::sort is usually IntroSort algorithm, which starts as a QuickSort, but switches to HeapSort if things go bad to avoid O(N^2) complexity (if recursion becomes too deep). So, std::sort at least uses std::sort_heap as a subroutine.

If you expect, that your data will be bad for QuickSort algorithm, it's better to start HeapSort manually, rather than wait while IntroSort performs some inefficient array partitions and only then switches to HeapSort.

So, worst case of HeapSort is better, than worst case of IntroSort - and if you need best worst case performance, you definitely should use HeapSort instead of IntoSort (std::make_heap + std::sort_heap instead of std::sort). But on the most inputs IntroSort performs faster.

And, of course, HeapSort uses O(1) additional memory instead of O(log(N)) for IntroSort.

P.S. Array of identical items are best case for HeapSort (requires O(N) time for FixDown heap implementation) and worst case for QuickSort without 3-way partition. If you have too much identical items in your array, it might be a good idea to use HeapSort instead of IntroSort.

Reasons:
  • Long answer (-1):
  • No code block (0.5):
  • Low reputation (1):
Posted by: Dmitry Zhitlukhin