SORTING SHUFFLED MONOTONE SEQUENCES

Authors
LEVCOPOULOS C PETERSSON O
Citation
C. Levcopoulos et O. Petersson, SORTING SHUFFLED MONOTONE SEQUENCES, Information and computation, 112(1), 1994, pp. 37-50
Citations number
20
Categorie Soggetti
Information Science & Library Science",Mathematics,"Computer Science Information Systems
Journal title
Information and computation → ACNP
ISSN journal
08905401
Volume
112
Issue
1
Year of publication
1994
Pages
37 - 50
Database
ISI
SICI code
0890-5401(1994)112:1<37:SSMS>2.0.ZU;2-8
Abstract
We present a new sorting algorithm that adapts to existing order withi n an input sequence. Let k be the smallest integer such that a sequenc e X of length n can be reduced to the empty sequence by the removal of k monotone, increasing or decreasing subsequences. The algorithm, Sla bsort, Sorts X in 0(n log k) time, without knowing k beforehand, which is optimal in a comparison-based model. (C) 1994 Academic Press, Inc.