Optimizing quicksort
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.