------- Comment #4 from sjhowe at dial dot pipex dot com 2008-04-21 18:51 ------- Yes. You want a partition that is O(1) that each time round eliminates N/2 elements (bearing in mind the post-condition for nth_element where iterators greater than the kth iterator have elements that are >= the kth element and iterators less than the kth iterator have elements that are <= the kth element) So median-of-3 or for large N is a must. And this is run for 3/2 * log2(N) steps.
If it has not converged by end of steps (so it has been a bad run) or new N is < some constant (making binary insertion sort worthwhile) then at that point you want the cheapest approximate median algorithm that is _guaranteed_ O(N). The algorithm is still O(N) as the choosing median and partitioning is occuring in serial. In this case, it is minimising the constant factor that matters. The median-of-median of 5 is well known But this approximate median is less well known. So it is the combination of (i) guaranteed O(N) partitioning (ii) cheapest constant factor (so minimising iterator traversal, copy ctor, swapping, comparing etc) I have not yet checked median of median-of-5 against this, but I believe (ii) works out cheaper. And if it works that there exists an even cheaper guranteed O(N) partitioning that finds an approximate median, gcc should use that. It does not matter if the exact median is found each time round just as long as N/2 elements are reduced each time round. I have also been alerted to a intraselect variation of nth_element() that looks promising. It is this: If you wanted the iterator that was 20% in from the start and you sampled elements to choose a partition element, instead of choosing an approximate median, choose the element that is 20%. So if the sample was 5 elements, choose the 2nd element. Now if partitioning was lop-sided but you reduced the number of elements drastically leaving a tiny amount as candidates, you have massively reduced the problem. This is brand new research in nth_element but I have not yet seen much analysis. Stephen Howe -- http://gcc.gnu.org/bugzilla/show_bug.cgi?id=35968
