On-line sorting of twisted sequences in linear time
type: Item
instance of: scholarly article
title: On-line sorting of twisted sequences in linear time
zbMATH Open document ID: 0647.68057
DOI: 10.1007/BF01934085
published in: BIT
publication date: 1988-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 68P10
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 4057016
zbMATH Keywords: sorting
zbMATH Keywords: worst-case complexity
zbMATH Keywords: twisted sequences
author: Franz Aurenhammer
MaRDI profile type: Publication
cites work: Q3948568
cites work: Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
cites work: Sorting jordan sequences in linear time using level-linked search trees
cites work: Q3779735
cites work: Q4057549
cites work: Q3219751
cites work: Q3694703
Recommended article: Tight bounds for online stable sorting
Recommended article: Online and offline algorithms for the sorting buffers problem on the line metric
Recommended article: On the time-space tradeoff for sorting with linear queries
Recommended article: Efficient linear-time ranking and unranking of derangements
Recommended article: Q4284248
Recommended article: Improved online algorithms for the sorting buffer problem on line metrics
Recommended article: An algorithm for online topological ordering
Recommended article: An ${\cal O}(n^{2.75})$ Algorithm for Online Topological Ordering
Recommended article: On the linear complexity for multidimensional sequences
Recommended article: Q3748193
description: scientific article; zbMATH DE number 4057016