Re: [math-fun] General way to avoid mispredicted branches (in sorting, & probably many other tasks)

On 6/2/14, Thomas Colthurst <thomaswc@gmail.com> wrote:

Those interested in this topic will probably enjoy http://research.microsoft.com/pubs/209622/patsort-sigmod14.pdf

"Patience is a Virtue: Revisiting Merge and Sort on Modern Processors"

--their abstract made it sound like "natural merge sort" an old algorithm. But actually there's a good deal more going on than that. Their pseudocode is very long and complicated, but yet amazingly imprecise, compared to virtually any sorting algorithm in any paper I ever saw. There seem to be no theorems there. These are just observations. I do not know what to make of it.