This is a follow-up to Quicksort functionLike 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<typename C>void insertion_sort(C low, C high) {    for (auto i = low; i < high; ++i) {        for (auto j = i; j != low && *j < *(j-1); --j) {            std::swap(*j, *(j-1));        }    }}template<typename C, typename I>I partition(C& c, I low, I high) {    auto p = *low;    I i = low;    I j = high;    while (true) {        while (i+1 != std::end(c) && *(++i) < p) {            if (i == high) {                break;            }        }        while (p < *(--j)) { }        if (i >= j) {            break;        }        std::swap(*i, *j);    }    std::swap(*low, *j);    return j;}template<typename C, typename I>void sort(C& c, I low, I high) {    if (high <= low+15) {        insertion_sort(low, high);        return;    }    I p = partition(c, low,high);    sort(c, low, p);    sort(c, p+1,high);}template<typename C>void sort(C& 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));}
Quicksort - follow-up
c++;algorithm;c++11;quick sort
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() <= 1 (as I would remove the exception)    return;}Special casing the std::end(c) just looks wrong.   while (i+1 != std::end(c) && *(++i) < 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 < high) && (*i < 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) >= 3// Note: it is called from sort when std::distance(low, high) > 15template<typename I>std::pair<I,I> partition(I low, I high) {    --high;    I   pivot   = high;    I   highBot = low;    I   lowTop  = high;    --lowTop;    while (highBot < lowTop) {        while ((highBot < high)  && (*highBot <= *pivot))   { ++highBot;}        while ((lowTop >= low)   && (*pivot < *lowTop))     { --lowTop;}        if (highBot < 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 >= low) && (*p == *lowTop); --lowTop) {}    return std::make_pair(lowTop+1, highBot+1);}Usage:std::pair<I,I> part = partition(low, high);sort(c, low, part.first);sort(c, part.second, high);