On-line sorting of twisted sequences in linear time (Q1104753)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | On-line sorting of twisted sequences in linear time |
scientific article |
Statements
On-line sorting of twisted sequences in linear time (English)
0 references
1988
0 references
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.
0 references
sorting
0 references
worst-case complexity
0 references
twisted sequences
0 references
0 references
