Why is QuickSort Single pivot faster than a tripartite partition?

Question

I am trying to get closer to the performance of QuickSorts (Single Pivot, 3-way and Dual Pivot).

Questions 1: I'm afraid that I have something missing in the implementation of the tripartite section. In a few runs against random input (out of 10 million) numbers, I could see that a single core always works better (although the difference is somewhere around 100 milliseconds for 10 million numbers).

I understand that the whole 3-way goal is not performance 0 (n ^ 2) for duplicate keys, which is very obvious when I run it to duplicate input. But is it true that for processing duplicate data a small penalty is adopted by a third-party? Or is my implementation bad?

Duplicate data:

• Quick Sort Basic: 888 milliseconds
• Quick Sort 3 Way: 522 millis
• Quick Sort Double Vault: 482 millis.

Random data:

• Quick Sort Basic: 1677 milliseconds
• Quick Sort 3 Way: 1717 millis
• Quick Sort Double Vault: 1595 millis.

Question 2:

The Dual Pivot implementation (link below) does not handle duplicates. It is required to execute 0 (n ^ 2) time. There is a good way to fast forward. I could see that we can check if the hinges are equal and increase the value of pivot1 until they are different from pivot2. Is this a fair implementation?

else if (pivot1==pivot2){ while (pivot1==pivot2 && lowIndex<highIndex){ lowIndex++; pivot1=input[lowIndex]; } } 

References to the implementation:

Root folder: https://github.com/arunma/dsa/tree/master/src/basics/sorting/quick

QuickSort (Single Pivot): https://github.com/arunma/dsa/blob/master/src/basics/sorting/quick/QuickSortBasic.java

QuickSort (3-way section): https://github.com/arunma/dsa/blob/master/src/basics/sorting/quick/QuickSort3Way.java

QuickSort (Dual Pivot): https://github.com/arunma/dsa/blob/master/src/basics/sorting/quick/QuickSortDualPivot.java

TestCase: https://github.com/arunma/dsa/blob/master/src/basics/sorting/quick/QuickSortTest.java

Answer 1

First of all, get rid of the suffix in the constructors to get the right comparison.

Secondly, the behavior is expected, since in the basic version you only perform a switch if you find the right candidate on both sides, that is, in QuickSortBasic.java

  while (true){ while (less(input[++i], input[pivotIndex])){ if (i==highIndex) break; } while (less (input[pivotIndex], input[--j])){ if (j==lowIndex) break; } if (i>=j) break; exchange(input, i, j); } 

while the 3way version you make the switch anyway if the element is not equal to the axis, that is, in QuickSort3Way.java

  while (i<=gt){ if (less(input[i],pivotValue)){ exchange(input, i++, lt++); } else if (less (pivotValue, input[i])){ exchange(input, i, gt--); } else{ i++; } }