Quicksort - follow-up This is a follow-up to 

Quicksort function

Like the previous code, this does not optimize for containers with large numbers of duplicate elements. How can I improve this code, particularly with iterators?

template&lt;typename C&gt;
void insertion_sort(C low, C high) {
    for (auto i = low; i &lt; high; ++i) {
        for (auto j = i; j != low &amp;&amp; *j &lt; *(j-1); --j) {
            std::swap(*j, *(j-1));
        }
    }
}

template&lt;typename C, typename I&gt;
I partition(C&amp; c, I low, I high) {
    auto p = *low;
    I i = low;
    I j = high;
    while (true) {
        while (i+1 != std::end(c) &amp;&amp; *(++i) &lt; p) {
            if (i == high) {
                break;
            }
        }
        while (p &lt; *(--j)) { }
        if (i &gt;= j) {
            break;
        }
        std::swap(*i, *j);
    }
    std::swap(*low, *j);
    return j;
}

template&lt;typename C, typename I&gt;
void sort(C&amp; c, I low, I high) {
    if (high &lt;= low+15) {
        insertion_sort(low, high);
        return;
    }
    I p = partition(c, low,high);
    sort(c, low, p);
    sort(c, p+1,high);
}

template&lt;typename C&gt;
void sort(C&amp; c) {
    if (std::begin(c) == std::end(c)) {
        throw std::out_of_range("no size");
    }
    if (c.size() == 1) {
        return;
    }
    std::random_shuffle(std::begin(c), std::end(c));
    sort(c, std::begin(c), std::end(c));
}
Sorting an empty array is perfectly valid.

if (c.size() == 0) {
    throw std::out_of_range("no size");
}


The result id an empty array. An exception is not the correct way to go.

OK optimize. An array of size 0 or 1 is already sorted.

if (c.size() == 1) {  // I would make this c.size() &lt;= 1 (as I would remove the exception)
    return;
}


Special casing the std::end(c) just looks wrong.

   while (i+1 != std::end(c) &amp;&amp; *(++i) &lt; p) {


I would say that if i+1 == high would be a better test. Also adding the ++ and * operators into the expression makes it really hard to read. I would go with:

    while ((i &lt; high) &amp;&amp; (*i &lt; p)) { ++i;}


The decrementing the j pointer should look exactly the same as the increment.

This is not tested (so may have bugs).
But this is how I would write partition.

// Note: this function require std::distance(low, high) &gt;= 3
// Note: it is called from sort when std::distance(low, high) &gt; 15
template&lt;typename I&gt;
std::pair&lt;I,I&gt; partition(I low, I high) {
    --high;
    I   pivot   = high;

    I   highBot = low;
    I   lowTop  = high;
    --lowTop;
    while (highBot &lt; lowTop) {
        while ((highBot &lt; high)  &amp;&amp; (*highBot &lt;= *pivot))   { ++highBot;}
        while ((lowTop &gt;= low)   &amp;&amp; (*pivot &lt; *lowTop))     { --lowTop;}
        if (highBot &lt; lowTop) {
            std::swap(*highBot, *lowTop);
        }
    }
    // At this point highBot and lowTop have just passed each other.
    // Thus highBot points to the first element greater than *pivot
    // and lowTop points to the last element smaller or equal to *pivot
    swap(*highBot, *pivot);

    // Now: highBot points to the pivot value and the value that was
    // at highBot is in the top end of the high range.

    // We want to to remove pivot value from the range of elements to be sorted.
    // so we want to sort the two ranges likes this:
    //
    //      [low..lowTop+1)
    //      highBot                 The pivot point removed from further sorting.
    //                              Note: lopTop+1 == highBot
    //      [highBot+1..high)
    //

    // Small optimization
    // If the value at lowTop is also equal to the pivot value
    // Then we can remove it from further sorting.
    for(; (lowTop &gt;= low) &amp;&amp; (*p == *lowTop); --lowTop) {}

    return std::make_pair(lowTop+1, highBot+1);
}


Usage:

std::pair&lt;I,I&gt; part = partition(low, high);
sort(c, low, part.first);
sort(c, part.second, high);