Parallel Partition

Partition does almost all of the work of quicksort. Further, the classic sequential partition, although wonderful, dominates the span of the quicksort algorithm. If we can parallelize partition, the span can be improved from ${\mathcal {O}}(n)$ down to ${\mathcal {O}}(\lg ^{k}{}n)$.

For N=16:

	<- - - - - - - - - - - - - - N - - - - - - - - - - - - - ->
^	partition [0, 16)
|	partition [0, 8)								partition [8, 16)
lg N	partition [0, 4)				partition [4, 8)				partition [8, 12)				partition [12, 16)
|	partition [0, 2)		partition [2, 4)		partition [4, 6)		partition [6, 8)		partition [8, 10)		partition [10, 12)		partition [12, 14)		partition [14, 16)
v	base	base	base	base	base	base	base	base	base	base	base	base	base	base	base	base

(Optional) Parallel Partition Challenge

The partitioning step can also be done in parallel with scan. While not particularly practical, it can get the CPL down to ${\mathcal {O}}(\lg ^{k}{}n)$.

class:	ParallelPartitioner.java
methods:	partitionRange
package:	sort.challenge.quick
source folder:	student/src/main/java

method: PivotLocation partitionRange(int[] data, int min, int maxExclusive) (parallel implementation required)

Testing Your Solution

Correctness

class:	ParallelPartitionerTestSuite.java
package:	sort.challenge.quick
source folder:	testing/src/test/java