News for hackers. Stuff that matters.

A comment on Proving that Android’s, Java’s and Python’s sorting algorithm is broken. Parent comment

Re:Proving that Android’s, Java’s and Python’s sorting algor... by nightcracker on Tuesday February 24, 2015 @10:15AM (#9100957)
No, it is fought by switching to heapsort if the recursion depth exceeds 2*log2(n).
[ Parent | on HN ]
Re:Proving that Android’s, Java’s and Python’s sorting algor... by sbi on Tuesday February 24, 2015 @10:49AM (#9101244)
Heapsort 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.
[ Parent | on HN ]
Re:Proving that Android’s, Java’s and Python’s sorting algor... by orlp on Tuesday February 24, 2015 @11:08AM (#9101446)
This is true, but the worst case of quicksort is so rare that this does not matter for average performance.
[ Parent | on HN ]