Обработка дубликатов ключей в быстрой сортировке

Question

Наивная быстрая сортировка потребует O(n^2) времени для сортировки массива, не содержащего уникальных ключей, потому что все ключи будут разделены либо до, либо после значения pivot. Существуют способы обработки дублированных ключей (например, описанный в Quicksort - оптимальный вариант). Предложенное решение работает только для раздела Hoare, но я реализовал раздел Lomuto. Чтобы справиться с дубликатами ключей, я чередовал перемещение дубликатов слева от центра и перемещение дубликатов справа от центра. Алгоритм работает примерно так:

//partition array from index start to end
select pivot element and move it to array[start]
boolean dupHandler=true;
int index=start;
for(i from start+1 to end)
     int val=array[start].compareTo(array[i]);
     if(val==0)
          if(dupHandler)
               swap array[++index] and array[i]
          dupHandler=!dupHandler;
     else if(val>0)
          swap array[++index] and array[i]
swap array[start] and array[index]

Есть ли лучший (более эффективный) способ обработки дубликатов ключей?

РЕДАКТИРОВАТЬ: мой код (как показано) требует, чтобы CompareTo было согласовано с равными (даже думал, что это не является обязательным)