I'm sorry to be so cynical, but I expect this to show up as a patented "new" invention, thanks to the patent office amnesia to anything that happened in computer science prior to perhaps 1980. Unless Knuth tells me that this is new, I would suspect that this is another example of wheel-reinvention. At 05:49 PM 6/2/2014, Thomas Colthurst 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"
Abstract:
The vast quantities of log-based data appearing in data centers has generated an interest in sorting almost-sorted datasets.
We revisit the problem of sorting and merging data in main memory, and show that a long-forgotten technique called Patience Sort can, with some key modifications, be made competitive with todayâs best comparison-based sorting techniques for both random and almost sorted data.
Patience sort consists of two phases: the creation of sorted runs, and the merging of these runs.
Through a combination of algorithmic and architectural innovations, we dramatically improve Patience sort for both random and almost-ordered data.
Of particular interest is a new technique called ping-pong merge for merging sorted runs in main memory.