3 ms·
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
by gjm11 17y ago
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.
- jongraehl 17y agoI 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.