Parallel Processing
Merge sort parallelizes well due to use of the divide-and-conquer method. A parallel implementation is shown in pseudo-code in the third edition of Cormen, Leiserson, and Stein's Introduction to Algorithms. This algorithm uses a parallel merge algorithm to not only parallelize the recursive division of the array, but also the merge operation. It performs well in practice when combined with a fast stable sequential sort, such as insertion sort, and a fast sequential merge as a base case for merging small arrays. Merge sort was one of the first sorting algorithms where optimal speed up was achieved, with Richard Cole using a clever subsampling algorithm to ensure O(1) merge. Other sophisticated parallel sorting algorithms can achieve the same or better time bounds with a lower constant. For example, in 1991 David Powers described a parallelized quicksort (and a related radix sort) that can operate in O(log n) time on a CRCW PRAM with n processors by performing partitioning implicitly.
Read more about this topic: Merge Sort
Famous quotes containing the word parallel:
“The parallel between antifeminism and race prejudice is striking. The same underlying motives appear to be at work, namely fear, jealousy, feelings of insecurity, fear of economic competition, guilt feelings, and the like. Many of the leaders of the feminist movement in the nineteenth-century United States clearly understood the similarity of the motives at work in antifeminism and race discrimination and associated themselves with the anti slavery movement.”
—Ashley Montagu (b. 1905)