An Optimal Sorting Algorithm for Presorted Sequences
Hiroyasu Hamamura, Junichi Miyao, Shin’ichi Wakabayashi · Institutional Repositories DataBase (IRDB) · 1991
A sorting algorithm is said to be optimal for presorted se- quences if it utilizes the presortedness of the input sequences.In this paper, we propose sequential and parallel sorting algorithms which are optimal with respect to three measures of presortedness, which are Runs, Radius, and $Rem$ .We assume an SM EREW MIMD model for the parallel algorithm.