Subj : Re: Arranging the keys problem To : comp.programming From : Roger Willcocks Date : Sun Oct 02 2005 09:11 pm "Willem" wrote in message news:slrndjq6fd.1gbb.willem@toad.stack.nl... > Richard wrote: > ) Quicksort is an overkill. The canonical in place O(n) solution is the > ) Dutch Flag Algorithm which, in the better quicksort implementations is > ) known as fat pivot partitioning. The point is that the first > ) partitioning pass suffices to solve the problem. > > That would be the slight tweak I was referring to. :-) > > As an aside: this was probably a homework question from a class, that is > leading up to quicksort. The fact that he wanted to sort red, white and > blue is a dead giveaway that Dutch National Flag is the intended solution. > Ref: http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Sort/Flag/ -- Roger .