Question on sorting
iaroslavski at mail.ru
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
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?
More information about the core-libs-dev