#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> quick_sort(vector<int> list)
{
   if (list.empty())
     return vector<int>();

   int head = list[0];
   vector<int> smaller;
   vector<int> larger;

   // filter
   copy_if (list.begin()+1, list.end(), back_inserter(smaller), [head](int i) {return i <= head;});
   copy_if (list.begin()+1, list.end(), back_inserter(larger), [head](int i) {return i > head;});

   //recursion
   auto sorted_smaller = quick_sort(smaller);
   auto sorted_larger = quick_sort(larger);

   //join vectors
   vector<int> ret;
   ret.insert(ret.end(), sorted_smaller.begin(), sorted_smaller.end());
   ret.push_back(head);
   ret.insert(ret.end(), sorted_larger.begin(), sorted_larger.end());

   return ret;
}


int main() {
  cout << "Quick sort!\n";

  vector<int> foo = {25,30,15,5,-5,-15,39};
  vector<int> bar=vector<int>();

  foo = quick_sort(foo);

  for(int v: foo)
     cout << v << ", ";

}