Re:Potential Quicksort replacement in java.util.Arrays with ...
by gjm11 on Friday September 11, 2009 @02:03PM
(#817777)
I thought "fat pivot" meant the approach to quicksort where you partition into { smaller, equal, larger } and then sort the three subarrays instead of two. I'm not sure what the "fat pivot problem" would be. Anyway, this new approach is a generalization of that -- fat pivoting is the special case where the two pivots are equal.
[ Parent
| on HN ]
Re:Potential Quicksort replacement in java.util.Arrays with ...
by jongraehl on Friday September 11, 2009 @03:04PM
(#817885)
I think you're right. I'm not sure if it's significant (because potentially there are fewer passes), but you end up having to swap more for a single pass. You also can get a stable in-place sort by treating the equal elements specially, which is why I'd do it.