Hello, I have performance question in sorting.
In an implementation of Dual-Pivot Quicksort 5 elements a[e1], a[e2], a[e3], a[e4], a[e5] where e1 = len/6, e2 = len/3, e3 = len/2, e4 = len*2/3, e5 = len*5/6, are sorted and then elements a[e2], a[e4] are taken as pivots. but if I take a[e1] and a[e3] as pivots, it works 2-3% faster on *random* inputs. I tried different sorting for these 5 elements: network, bubble, insertion - with a[e1] and a[e3] pivots it is faster than with a[e2] and a[e4]. If I sort these 5 elements in descending order, it works faster with a[e5] and a[e3] pivots. Do you have any idea why it happens? Thank you, Vladimir
