On-line sorting of twisted sequences in linear time
A sequence of real numbers is called twisted if it can be produced from the
sorted sequence by repeatedly reversing the order of consecutive
subsequences. It is shown that twisted sequences constitute a class of
exponentially many members each of which can be recognized and sorted, by a
simple on-line algorithm, in linear time.
Reference: F. Aurenhammer.
On-line sorting of twisted sequences in linear time.
BIT, 28:194-204, 1988.
[IIG-Report-Series 232, TU Graz, Austria, 1987].