With many equal keys, ordinary quick sort wastes time re-sorting them. Write ThreeWayQuick using Dijkstra's three-way partition with pivot a[low] and three indexes lt, i, gt:
a[i] < pivot: swapa[lt]anda[i], advance both;a[i] > pivot: swapa[i]anda[gt], decreasegt(do not advancei);- equal: advance
i.
Afterwards a[lt..gt] equals the pivot and is finished; recurse only on the two outer parts. Count one comparison per loop iteration. Print the array after the first partition with the bounds of the equal block, the sorted array, the comparisons and the recursion depth (the top-level call is depth 1; calls on fewer than two elements do not count).
For the input
9
4 9 4 1 4 7 1 9 4
the program prints
first partition (pivot 4): [1, 1, 4, 4, 4, 4, 9, 7, 9], equal block 2..5
sorted: [1, 1, 4, 4, 4, 4, 7, 9, 9]
comparisons: 11, recursion depth: 2