Simplified odd-even sort using multiple shift-register loops

Abstract

By using an N-loop shift-register structure called a uniform ladder, N records can be sorted by a simplified adaptation of the odd-even transposition-sort algorithm to finish in (N + 1)/2 loop times (periods) using (N - 1) comparators. The sorting can be overlapped with input/output; the percentage of unoverlapped sorting times is less than 20% of the total time with a single ladder, less than 6% using two ladders, and is zero with a sufficient number of ladders. © 1978 Plenum Publishing Corporation.