Optimizing quicksort I created simple quicksort algorithm using iterators. I'm happy with implementation but not with its speed. Profiler tells me that the slowest operation here is std::iter_swap. I don't really know how to improve this code. Note that I am not asking for different kind of quicksort algorithm but about improving this one.

#include &lt;iterator&gt;
#include &lt;utility&gt;
#include &lt;functional&gt;

template &lt;typename RandomIt, typename Compare = std::less_equal&lt;&gt;&gt;
void Sort::QuickSort(RandomIt first, RandomIt last, Compare compare = Compare())
{
    if (std::distance(first, last) &lt;= 1) return;
    RandomIt pivot = Partition(first, last, compare);
    QuickSort(first, pivot, compare);
    QuickSort(std::next(pivot, 1), last, compare);
}

template &lt;typename RandomIt, typename Compare&gt;
RandomIt Sort::Partition(RandomIt first, RandomIt last, Compare compare)
{
    RandomIt pivot = MedianOf3(first, last, compare);
    RandomIt i = first;
    for (RandomIt j = first; j != pivot; ++j)
        if (compare(*j, *pivot)) {
            std::iter_swap(i, j);
            ++i;
        }
    std::iter_swap(i, pivot);
    return i;
}

template &lt;typename RandomIt, typename Compare&gt;
RandomIt Sort::MedianOf3(RandomIt first, RandomIt last, Compare compare)
{
    auto collectionSize = std::distance(first, last);
    RandomIt middle = std::next(first, collectionSize / 2);
    RandomIt targetPivot = std::prev(last, 1);
    if (compare(*middle, *first))
        std::iter_swap(middle, first);
    if (compare(*targetPivot, *first))
        std::iter_swap(targetPivot, first);
    if (compare(*middle, *targetPivot))
        std::iter_swap(middle, targetPivot);
    return targetPivot;
}


For testing I used vectors of 100 000 random elements. This code average sorting time is about 1626 ms on my machine and std::sort on the same set of data performs 10 times better, around 163 ms. I know that std::sort uses introsort but still quicksort shouldn't be 10 times slower.
To get this code to compile I had to add the Sort namespace definition:

namespace Sort
{
    template &lt;typename RandomIt, typename Compare = std::less_equal&lt;&gt;&gt;
    void QuickSort(RandomIt first, RandomIt last, Compare compare = Compare());

    template &lt;typename RandomIt, typename Compare&gt;
    RandomIt Partition(RandomIt first, RandomIt last, Compare compare);

    template &lt;typename RandomIt, typename Compare&gt;
    RandomIt MedianOf3(RandomIt first, RandomIt last, Compare compare);
}


And I had to remove the default argument from the redeclaration of Sort::QuickSort:

template &lt;typename RandomIt, typename Compare = std::less_equal&lt;&gt;&gt;
void Sort::QuickSort(RandomIt first, RandomIt last, Compare compare)


Review requests should have issues like that already accounted for.



The performance of the Partition() function can be improved by doing fewer swaps.  The current loop swaps when *j &lt; *pivot, without considering whether *i is less or greater than *pivot.  Instead, we can use two iterators, and advance them towards each other, swapping only when the ascending iterator points to an item greater than pivot and the descending iterator points to one smaller than pivot.  The tricky bit is to avoid the iterators passing each other without terminating.