Most men age twenty-six can boast few accomplishments.
Sir Charles Antony Richard Hoare is not most men. At that age, C.A.R. Hoare invented Quicksort (pdf).
Quicksort is typically more efficient than other comparison sorting algorithms in both auxiliary memory requirements and execution cycles. Yet, it shares the same common case time complexity limit of its peers - O(n*log n).
Parallelism is the tool to effectively breach that barrier. As a binary tree sort, Quicksort is especially suited for parallelism since multiple threads of execution can work on sorting task parts without synchronized data access.
We will detail two effective synchronization policies for parallel Quicksort in Java. One is usable in production now, one is coming soon in JDK 7.
All of the code here is condensed for rapid comprehension.
To see more proper implementations of the concepts, visit https://github.com/pmbauer/parallel.
For a quick refresher on the serial version of Quicksort, the Algolist Quicksort article is excellent; its explanation and visuals are clearer than C.A.R. Hoare's Oxford journal paper. Of note, all our parallel implementations will use in-place partitioning.
Read full article from (def title nil): Quick(er)sort, Parallelism, and Fork/Join in JDK7
No comments:
Post a Comment