Modern, C++ compliant, quick sort
Correctness

Fix build errors

My compiler indicates that your typedef statement is missing typename before std::iterator_traits&lt;BidirIt&gt;::difference_type dt; Additionally, you can replace the typedef with a using statement, which is more modern:

using dt = typename std::iterator_traits&lt;BidirIt&gt;::difference_type;


Adhere to iterator operations

The line:

auto pivot = first + size / dt(2);


Uses the + operator, which bidirectional iterators do not support. Calling your sort on a std::list will fail to compile. You can make your code compliant with bidirectional iterators by changing the above line to:

const auto offset = size / dt(2);
auto pivot = std::next(first, offset);


Squash the bug!

I don't know the cause, but your program appears to loop forever when I give your algorithm the sequence: 1,8,4,6,5,2,0,3. This is almost certainly not desired behavior.

Code Simplicity

Return the new pivot

You can avoid taking the pivot by reference by changing partition() to return the pivot value. The new function signature would be:

template&lt;typename BidirIt,
typename Comparator = std::less&lt;typename std::iterator_traits&lt;BidirIt&gt;::value_type&gt;&gt;
BidirIt partition(BidirIt first,
                  BidirIt last,
                  BidirIt pivot,
                  Comparator cmp = Comparator())


And then simply return pivot; at the end of the function. But then this function signature looks familiar:

Use the standard library, Luke!

There already exists a partition() function in the standard library. You can replace your entire partition function with it, and simplify sort_quick():

    pivot = std::partition(first, last, [&amp;] (auto value)
                           {
                               return cmp(value, *pivot);
                           });


The use of auto in the lambda is a C++14 feature, you will have to write out the correct type if you can only use C++11. Also, using std::partition fixes the loop-forever bug on my "bad" input, but still doesn't quite give correct results.

Minor Issues

Unused comparator

sort_quick() accepts a comparator function argument, but the comparator is never used inside the body of the function.

Restrict Iterator types

Currently you rely on convention that your iterator types are bidirectional. You could produce nicer error messages by using static_assert, possibly like this:

using category = typename std::iterator_traits&lt;BidirIt&gt;::iterator_category;
static_assert(std::is_base_of&lt;std::bidirectional_iterator_tag, category&gt;::value, "This algorithm requires bidirectional iterators.");