Parallel Sorting Algorithms

Description

Content: Front Cover Parallel Sorting Algorithms Copyright Page Dedication Table of Contents Preface Chapter 1. Introduction 1.1 Motivation 1.2 The Sorting Problem 1.3 Parallel Models of Computation 1.4 Parallel Algorithms 1.5 Lower Bounds on the Parallel Sorting Problem 1.6 Organization of the Book 1.7 Bibliographical Remarks References Chapter 2. Networks for Sorting 2.1 Introduction 2.2 Enumeration Sort 2.3 Sorting by Odd-Even Merging 2.4 Sorting Based on Bitonic Merging 2.5 Bibliographical Remarks References Chapter 3. Linear Arrays 3.1 Introduction. 3.2 Odd-Even Transposition Sort3.3 Merge-Splitting Sort 3.4 Mergesort on a Pipeline 3.5 Enumeration Sort 3.6 Bibliographical Remarks References Chapter 4. The Perfect Shuffle 4.1 Introduction 4.2 Bitonic Sorting Using the Perfect Shuffle 4.3 An Optimal Merge-Splitting Algorithm 4.4 Bibliographical Remarks References Chapter 5. Mesh-Connected Computers 5.1 Introduction 5.2 Model of Computation 5.3 The Sorting Problem 5.4 A Lower Bound 5.5 Sorting on the Mesh 5.6 An Optimal Algorithm 5.7 Bibliographical Remarks References Chapter 6. Tree Machines 6.1 Introduction. 6.2 Minimum Extraction6.3 Bucket Sorting and Merging 6.4 Median Finding and Splitting 6.5 Bibliographical Remarks References Chapter 7. Cube-Connected Computers 7.1 Introduction 7.2 Model of Computation 7.3 The Sorting Problem 7.4 The Sorting Machine 7.5 Sorting on the Cube 7.6 Bibliographical Remarks References Chapter 8. Shared-Memory SIMD Computers 8.1 Introduction 8.2 Model of Computation 8.3 A Parallel Algorithm for Selection 8.4 Sorting on a Shared-Memory SIMD Computer 8.5 Bibliographical Remarks References Chapter 9. Asynchronous Sorting on Multiprocessors. 9.1 Introduction9.2 Running Asynchronous Algorithms 9.3 Asynchronous Sorting by Enumeration 9.4 Asynchronous Quicksort 9.5 Bibliographical Remarks References Chapter 10. Parallel External Sorting 10.1 Introduction 10.2 External Sorting on a Tree 10.3 External Sorting on a Pipeline 10.4 Bibliographical Remarks References Chapter 11. Lower Bounds 11.1 Introduction 11.2 A Review of Lower Bounds 11.3 Counting Comparisons 11.4 Broadcasting 11.5 A Lower Bound on Tree Sorting 11.6 Bibliographical Remarks References Author Index Subject Index.