Roughly Sorting: Sequential and Parallel Approach
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

Journal of information processing 12(2), 154158, 19890830
Information Processing Society of Japan (IPSJ)