3 ms·
No, it is fought by switching to heapsort if the recursion depth exceeds 2*log2(n).
by nightcracker 12y ago
No, it is fought by switching to heapsort if the recursion depth exceeds 2*log2(n).
- sbi 12y agoHeapsort has poor cache performance though. Its asymptotic complexity depends on the assumption that memory access is O(1), which is not borne out in practice.
- nightcracker 12y agoThis is true, but the worst case of quicksort is so rare that this does not matter for average performance.