4 ms·
>> 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 so
by phkahler 7y ago
>> 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.