Question on sorting

Vladimir Iaroslavski iaroslavski at
Fri Jul 30 18:55:00 UTC 2010


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,

More information about the core-libs-dev mailing list