std::partition called twice for quick sort

Viewed 498

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.

1 Answers
Related