#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>
#include <forward_list>
 
namespace ranges = std::ranges;
 
template <std::permutable I, std::sentinel_for<I> S>
void quicksort(I first, S last)
{
   if(first == last) {
       return;
   }
 
   auto pivot = *ranges::next(first, ranges::distance(first,last)/2, last);
   auto middle1 = ranges::partition(first, last, [pivot](const auto& em){
       return em < pivot;
   });
   auto middle2 = ranges::partition(middle1, last, [pivot](const auto& em){
       return !(pivot < em);
   });
   quicksort(first, middle1);
   quicksort(middle2, last);
}
 
int main()
{
    std::vector<int> v = {0,1,2,3,4,5,6,7,8,9};
    std::cout << "Original vector:\n    ";
    for(int elem : v) {
        std::cout << elem << ' ';
    }
 
    auto it = ranges::partition(v, [](int i){return i % 2 == 0;});
 
    std::cout << "\nPartitioned vector:\n    ";
    ranges::copy(ranges::begin(v), it, std::ostream_iterator<int>(std::cout, " "));
    std::cout << " * ";
    ranges::copy(it, ranges::end(v), std::ostream_iterator<int>(std::cout, " "));
 
    std::forward_list<int> fl = {1, 30, -4, 3, 5, -4, 1, 6, -8, 2, -5, 64, 1, 92};
    std::cout << "\nUnsorted list:\n    ";
    for(int n : fl) {
        std::cout << n << ' ';
    }
    std::cout << '\n';
 
    quicksort(ranges::begin(fl), ranges::end(fl));
    std::cout << "Sorted using quicksort:\n    ";
    for(int fi : fl) {
        std::cout << fi << ' ';
    }
    std::cout << '\n';
}