В среднем он использует меньше свопов, по крайней мере, если в массиве не так уж мало разных элементов.
Алгоритм «голландского флага» использует один своп на элемент, не равный сводному значению, поэтому
n - multiplicity(pivot)
свопы.
Альтернатива, которая меняет местами элементы, равные оси, сначала на концы массива, дважды меняет каждый элемент, равный точке поворота (один раз на один конец и, наконец, на середину), и меняет пары a[i], a[j] на i < j и a[j] < pivot < a[i], это
2*multiplicity(pivot) + count(bad_pairs)
свопы. Количество плохих пар не может быть больше чем (n - multiplicity(pivot))/2 и обычно (случайный массив) меньше, вне моей головы, я бы ожидал что-то вроде (n-multiplicity(pivot))/4 или меньше в среднем. Так что если multiplicity(pivot) < n/5, альтернатива гарантированно использует меньше свопов, и если моя оценка верна, в среднем она будет использовать меньше свопов, если multiplicity(pivot) < 3*n/11.
Так что, если вы априори знаете, что в массиве только очень мало (<= 5 или около того) различных элементов, я думаю, что «голландский флаг» будет лучше, но в целом альтернатива будет использовать меньше свопов, пока детали для сортировки стали довольно маленькими. </p>