# Handling duplicate keys in quicksort

A naïve quicksort will take O(n^2) time to sort an array containing no unique keys, because all keys will be partitioned either before or after the pivot value. There are ways to handle duplicate keys (like one described in Quicksort is Optimal). The proposed solution only works for the Hoare partition, but I've implemented the Lomuto partition. To deal with duplicate keys, I alternated between moving duplicates to the left of the pivot and moving duplicates to the right of the pivot. Here's my quicksort (ignore the lack of generics):

public static void swap(Comparable[] sort, int a, int b){
Comparable temp=sort[a];
sort[a]=sort[b];
sort[b]=temp;
}
public static void quicksort(Comparable[] sort, int start, int end){
while(end-start>1){//normal case
int pivot=gen.nextInt(end-start)+start;//random pivot
swap(sort, pivot, start);
int index=start;//walking index
boolean dupHandler=false;//init to true works also
for(int i=start+1; i<end; ++i){//Lomuto partition
int val=sort[start].compareTo(sort[i]);
if(val>0 || ( val==0 && (dupHandler=!dupHandler) ) )
swap(sort, ++index, i);
}
swap(sort, start, index);
if(index-start<end-index-1){//recurse into smaller partition
quicksort(sort, start, index);
start=index+1;//use iteration for other partition
}
else{
quicksort(sort, index+1, end);
end=index;
}
}
}


Is there a better (more efficient) way to handle duplicate keys? If not, is there any way to significantly improve my code?

• This is code review, not pseudocode review. If you want reviews of your code, please post your actual code. Aug 5, 2011 at 4:02
• Naive quicksort is O(n^2) full stop; it has nothing to do with duplicate keys.
– Rafe
Aug 5, 2011 at 4:56
• @Winston Code is posted Aug 5, 2011 at 5:02
• @Rafe I know, but even a quicksort with random pivot selection will degenerate to the O(n^2) case if all keys are equal. Aug 5, 2011 at 5:07
• Consider sorting an ascending list of numbers. To guarantee O(n log n) you do quicksort for the first k log n levels of recursion, then back off to a guaranteed O(n log n) sort, albeit with a larger constant factor than quicksort (e.g., merge sort).
– Rafe
Aug 5, 2011 at 5:10

1. Use a swap function rather then repeating the three lines required to swap elements three times
2. Put spaces around your operators
3. You avoid recursing for the second partition. I don't think the performance gain from this is sufficient for the extra complexity in your code.

Rather then swapping before/after for the element equal to the pivot, count the number of elements equal to the pivot. Then when you sort the subarray make the one subarray shorter so as not to sort the elements equal to the pivot.

Another issue as Rafe has noted is that there are other issues besides duplicate keys that can cause a O(n^2) behavior. Your code doesn't handle any of those.

• 1. I just changed the code inside the loop so that the lines aren't repeated. Is that better or worse than before? 2. Too lazy to do that now, but you're right 3. The added complexity doesn't seem like much to me; it's just one extra if-else statement 4. I like that way of handling duplicates, I'll implement it when it's not 2AM 5. I do choose a random pivot... the only more efficient pivot choices are the median-of-three (still no O(nlogn) guarantee) and the O(n) selection algorithms (these esnure O(nlogn) time but increase those pesky constant factors) Aug 5, 2011 at 5:54
• I don't know how to put newlines in comments... sorry 'bout that Aug 5, 2011 at 5:55
• @Derek, 1. you are still repeating the swap code three times. 3. There is also the while loop (which would be an if statement) but just generally your code obscures the nature of the quicksort algorithm. 5. Choosing a random pivot is good, but that doesn't guarantee you won't have problems. You could randomnly choose bad pivots. Aug 5, 2011 at 6:07
• 1. OH RIGHT... I forgot about the other swaps... 3. The complexity of the code is of no concern, so long as I can understand it; I'm coding this for fun (yes, I do that) 5. I'm open to any pivot-selection algorithms; any one in particular that you recommend? Aug 5, 2011 at 6:12
• @Derek, 3. This is code review, I reserve the right to complain that your code has been made less readable for probably undetectable performance gains. You can reserve the right to ignore me. :) 5. I'm not suggesting a better pivot selection algorithm. I'm wondering whether your strategy has any advantage over something like introsort. Aug 5, 2011 at 6:22