sort-functional-style-no-templates.cpp

#include <vector>
#include <functional>
#include <algorithm>
#include <utility>
#include <type_traits>
#include <iostream>

template<typename T> auto read_vector() {
    return std::vector<T>{std::istream_iterator<T>{std::cin}, std::istream_iterator<T>{}};
}

template<typename T> auto concat(std::vector<T> a, const std::vector<T>& b, const std::vector<T>& c) {
    a.insert(std::end(a), std::begin(b), std::end(b));
    a.insert(std::end(a), std::begin(c), std::end(c));

    return a;
}

template<typename T> auto to_vector(T&& t) {
    return std::vector<typename std::remove_const<typename std::remove_reference<T>::type>::type>{ std::forward<T>(t) };
}

template<typename T, typename F> auto filter(const std::vector<T>& v, F&& f) {
    auto ret = std::vector<T>{};
    std::copy_if(std::begin(v), std::end(v), std::back_inserter(ret), std::forward<F>(f));
    return ret;
}

template<typename T> std::vector<T> quicksort(const std::vector<T>& v) {
    return v.size() > 1 ? concat(
        quicksort(filter(v, std::bind(std::greater<T>{}, v.front(), std::placeholders::_1))),
        to_vector(v.front()),
        quicksort(filter(v, std::bind(std::less<T>{}, v.front(), std::placeholders::_1)))
    ) : v;
}

int main() {
    const auto v = quicksort(read_vector<int>());

    std::copy(std::begin(v), std::end(v), std::ostream_iterator<int>{std::cout, " "});
    std::cout << std::endl;
}