The Library
Improved sorting networks with O(log n) depth
Tools
Tools
Tools
Paterson, Michael S. (1987) Improved sorting networks with O(log n) depth. Coventry, UK: University of Warwick. Department of Computer Science. (Department of Computer Science Research Report). (Unpublished)
|
PDF
WRAP_cs-rr-89.pdf - Requires a PDF viewer. Download (15Mb) | Preview |
Abstract
The sorting network described by Ajtai, KomlOs and Szemeredi was the first to achieve a depth of O(Iog n). The networks introduced here are simplifications and improvements based strongly on their work. While the constants obtained for the depth bound still prevent the construction being of practical value, the structure of the presentation offers a convenient basis for further development.
| Item Type: | Report | ||||
|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||
| Library of Congress Subject Headings (LCSH): | Computer networks | ||||
| Series Name: | Department of Computer Science Research Report | ||||
| Publisher: | University of Warwick. Department of Computer Science | ||||
| Place of Publication: | Coventry, UK | ||||
| Official Date: | January 1987 | ||||
| Dates: |
|
||||
| Number: | Number 89 | ||||
| Number of Pages: | 21 | ||||
| DOI: | CS-RR-089 | ||||
| Institution: | University of Warwick | ||||
| Theses Department: | Department of Computer Science | ||||
| Status: | Not Peer Reviewed | ||||
| Publication Status: | Unpublished | ||||
| Reuse Statement (publisher, data, author rights): | M.S. Paterson, “Improved Sorting Networks with O(log n) Depth”, <i>Algorithmica</i> <b>5</b>, pp. 75-92 (1990) | ||||
| Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
