@article{oai:ipsj.ixsq.nii.ac.jp:00059782,
 author = {Tom, Altman and Yoshihide, Igarashi and Tom, Altman and Yoshihide, Igarashi},
 issue = {2},
 journal = {Journal of Information Processing},
 month = {Aug},
 note = {We study sequential and parallel algorithms on roughly sorted sequences. A sequence a = (a_l  a_2  . . .   a_n) is k-sorted if for all 1&les;i j&les;n i<j- k implies a_i&les;a_j. We first show a real-time algorithm for determining if a given sequence is k-sorted and an O(n)-time algorithm for finding the smallest k for a given sequence to be k-sorted. Next  we give two sequential algorithms that merge two k-sorted sequences to form a k-sorted sequence and completely sort a k-sorted sequence. Their running times are O(n) and O(n log k)  respectively. Finally  parallel versions of the complete-sorting 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., We study sequential and parallel algorithms on roughly sorted sequences. A sequence a = (a_l, a_2, . . . , a_n) is k-sorted if for all 1&les;i,j&les;n,i<j- k implies a_i&les;a_j. We first show a real-time algorithm for determining if a given sequence is k-sorted and an O(n)-time algorithm for finding the smallest k for a given sequence to be k-sorted. Next, we give two sequential algorithms that merge two k-sorted sequences to form a k-sorted sequence and completely sort a k-sorted sequence. Their running times are O(n) and O(n log k), respectively. Finally, parallel versions of the complete-sorting 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.},
 pages = {154--158},
 title = {Roughly Sorting: Sequential and Parallel Approach},
 volume = {12},
 year = {1989}
}