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.