What is the logic behind the two calls to std::partition from the example from http://en.cppreference.com/w/cpp/algorithm/partition? I understand the high level design of the quick sort algorithm but I'm having difficulties fully understanding this implementation.
template <class ForwardIt>
void quicksort(ForwardIt first, ForwardIt last)
{
if(first == last) return;
auto pivot = *std::next(first, std::distance(first,last)/2);
ForwardIt middle1 = std::partition(first, last,
[pivot](const auto& em){ return em < pivot; });
ForwardIt middle2 = std::partition(middle1, last,
[pivot](const auto& em){ return !(pivot < em); });
quicksort(first, middle1);
quicksort(middle2, last);
}
Thank you.