On-line sorting of twisted sequences in linear time

F. Aurenhammer

Abstract:

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].