Quick(er)sort, Parallelism, and Fork/Join in JDK7

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. Quick(er)sort, Parallelism, and Fork/Join in JDK7 full article

site menu

Back to top