Read/Search this Article
Abstract
We study sequential and parallel algorithms on roughly sorted sequences. A sequence a = (a_l, a_2, . . . , a_n) is ksorted if for all 1<≤i,j<≤n,i<jk implies a_i<≤a_j. We first show a realtime algorithm for determining if a given sequence is ksorted and an O(n)time algorithm for finding the smallest k for a given sequence to be ksorted. Next, we give two sequential algorithms that merge two ksorted sequences to form a ksorted sequence and completely sort a ksorted sequence. Their running times are O(n) and O(n log k), respectively. Finally, parallel versions of the completesorting algorithm are presented. Their parallel running times are O(f(2k) 1og k), where f(t) is the computing time of an algorithm used for finding the median among t elements.
Journal
 Journal of information processing [List of Volumes]

Journal of information processing 12(2), 154158, 19890830 [Table of Contents]
Information Processing Society of Japan (IPSJ)
Share