Details
-
Improvement
-
Status: Closed
-
Major
-
Resolution: Fixed
-
None
-
None
-
None
-
Reviewed
Description
The current implementation of QuickSort naively partitions on either side of the pivot. We can improve this by partitioning on either side of the set of values equal to the pivot. This assumes that comparing keys is expensive compared to swaps and index comparisons (which it certainly is in MapTask, and should be in general).