Quasi-Stable Patience Sort for ATS/Postiats
-------------------------------------------

I call this implementation ‘quasi-stable’ because stability of the
result depends on determining whether two elements are equal and then
comparing their original indices. This is little extra computation if
your patience_sort$cmp procedure is one that tests for equality, but
if your patience_sort$cmp procedure is really just a less-than
predicate (or if you use patience_sort$lt instead) then the sort will
be unstable. In what I am calling a ‘true’ stable sort--for instance,
a stable mergesort--stability arises without any extra computation
whatsoever.

‘Patience sort’ is an old method of sorting, inspired by the solitaire
card game Klondike (which sorts the cards face-up as you play it). You
‘deal’ the data into Klondike-like sorted piles, and then do a k-way
merge of the sorted piles. Patience sort seemed too ‘heavy’ until I
implemented it in Fortran without resorting to linked lists. So the
stuff here goes back to my Rosetta Code contribution of a Fortran
implementation, followed by my migration of that implementation to
other languages (including at least Ada, Mercury, Modula-2, Pascal,
and ATS).

This sort should perform O(n log n) in the worst case and O(n) in the
best case.