quicksort - クイックソートで重複キーを処理する

Question

ナイーブクイックソートでは、すべてのキーがピボット値の前または後に分割されるため、一意のキーを含まない配列をソートするのにO（n ^ 2）時間がかかります。重複キーを処理する方法があります（クイックソートで説明されているものは最適です）。提案されたソリューションは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がequalsと一致している必要があります（それが要件ではないとしても）