News for hackers. Stuff that matters.
Re:Lomuto's Comeback by phkahler on Sunday May 17, 2020 @04:09PM (#23214963)
>> Sorting is the case study but not the insight. I think the cool/surprising part of the article is that doing more work can be faster

Yeah, I figured heap sort should be the standard because it has a worst case O(n*log(n)) complexity. But it does tend to do more swaps (a smarter implementation can avoid many writes), and the memory access is very cache-unfriendly. In practice it's just not used.

There are no comments on this comment yet.