<p>I have actually studied this extensively in my paper. <a href="https://arxiv.org/ftp/arxiv/papers/1505/1505.00558.pdf" rel="nofollow">https://arxiv.org/ftp/arxiv/papers/1505/1505.00558.pdf</a></p>

<p>The short answer is, NO. Dual Pivot doesn't perform as well when compared to a high end version of quicksort when swapping large elements. Look at figures 22 and 23.</p>
Dual pivot quicksort in face of expensive swaps
<p><em>Moved this question over to <a href="https://softwareengineering.stackexchange.com/questions/253350/dual-pivot-quicksort-in-face-of-expensive-swaps">Programmers</a>, as it didn't seem theoretical enough for CS.</em><br>
<strong>TLDR</strong><br>
Has anyone tested dual pivot quicksort performance with expensive-to-swap elements? It seems that in this case, it should massively underperform standard quicksort.</p>

<p><br>
<strong>Backstory</strong><br>
Inspired by recent "question" <a href="https://stackoverflow.com/questions/24650626/how-to-implement-classic-sorting-algorithms-in-modern-c">here on stack overflow</a>, I decided to go and implement non trivial versions of given sorts (<a href="http://en.wikipedia.org/wiki/Introsort" rel="nofollow noreferrer">introsort</a>, <a href="http://en.wikipedia.org/wiki/Quicksort" rel="nofollow noreferrer">quicksort</a> with <a href="http://en.wikipedia.org/wiki/Dutch_national_flag_problem" rel="nofollow noreferrer">3-way partition</a>, median of 3 pivot selection, small block insertion sort etc).</p>

<p>During some research I also came upon dual pivot quicksort, <a href="http://docs.oracle.com/javase/7/docs/api/java/util/Arrays.html#sort(int[])" rel="nofollow noreferrer">which is the current implementation of quicksort in Java standard library</a>. Generally it claims that it is always at least as good as standard quicksort, and empirical testing seemed to support it. (Which is the reason it is the current implementation.)</p>

<p>However, it seems that no STL implementation uses dual pivot quicksort for the quicksort phase of introsort, which made me wonder why. After more research I found <a href="http://arxiv.org/pdf/1304.0988.pdf" rel="nofollow noreferrer">this paper</a>. It says that while dual pivot quicksort performs on average 5% less comparisons, it performs significantly more swaps. (Approximately 80% more) Obviously, since Java has only primitives and reference types, swapping is always cheap. (Even so, it uses this sort only for primitives, because it is not stable)</p>

<p>So I wanted to see whether someone already tested standard quicksort vs dual pivot quicksort when elements are expensive to swap and has the numbers (and possibly source) lying around, or whether I will have to test this myself.</p>

<p><strong>This question is specifically about quick sort variants.</strong></p>