Parallel Sorting on a Re-circulating Systolic Sorter
F.S. Wong · The Computer Journal · 1984
In this paper, we present a re-circulating systolic sorting array and two sorting algorithms. The correctness of these algorithms is proved and general operational constraints are examined. These algorithms are amenable to VLSI implementation owing to the following attributes: (1) the simple control patterns of the algorithms, (2) the regular, repetitive and near-neigbour type of interconnection among the comparators, and (3) the systolic data movement. The sorting array is also well-suited for fabrication on shift-register type of storage and logic devices–such as magnetic bubble memories (MBMs) and charge-coupled devices (CCDs)–because of its closed-loop structure. The number of comparators and sorting time are both in O(N) where N is the number of items to be sorted. A hardware termination methods is incorporated into the control unit of the sorter, so that the sorting process can be terminated within a bounded time after the input list is in the desired order.