Name
Abstract | ||
|---|---|---|
A parallel algorithm for sorting n data items in O(n) steps is presented. Its simple structure and the fact that it needs local communication only make it suitable for an implementation in VLSI technology. The algorithm is based on a merge algorithm that merges four subfiles stored in a mesh-connected processor array. This merge algorithm is composed of the perfect shuffle and odd-even-transposition sort. For the VLSI implementation a systolic version of the algorithm is presented. The area and time complexities for a bit-serial and a bit-parallel version of this implementation are analyzed. |
Year | DOI | Venue |
|---|---|---|
1985 | 10.1109/TC.1985.1676603 | IEEE Trans. Computers |
Keywords | Field | DocType |
Odd-even-transposition sort,VLSI algorithms,VLSI complexity,mesh-connected processor array,perfect shuffle,sorting,systolic array,Odd-even-transposition sort,VLSI algorithms,VLSI complexity,mesh-connected processor array,perfect shuffle,sorting,systolic array | Merge algorithm,Counting sort,Merge sort,Parallel algorithm,Computer science,sort,Parallel computing,In-place algorithm,Sorting,Sorting algorithm | Journal |
Volume | Issue | ISSN |
34 | 7 | 0018-9340 |
Citations | PageRank | References |
29 | 5.91 | 5 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| H. -W. Lang | 1 | 47 | 9.32 |
| M. Schimmler | 2 | 45 | 8.14 |
| H. Schmeck | 3 | 330 | 32.82 |
| H. Schroder | 4 | 29 | 5.91 |