#include <iostream>
#include <vector>
#include <iterator>
#include <iterator>
#include <unordered_map>
#include <map>
#include <type_traits>
#include <algorithm>
using std::vector;

template<typename RandomIt>
void InsertionSort(RandomIt begin, RandomIt end) {
    for (auto it = begin + 1; it < end; ++it) {
        auto current_value = *it;
        auto prev_it = std::prev(it);
        while (prev_it >= begin && *prev_it > current_value) {
            *std::next(prev_it) = *prev_it;
            --prev_it;
        }
        *std::next(prev_it) = current_value;
    }
}

template<typename RandomIt,class = typename std::enable_if<std::is_integral<typename std::iterator_traits<RandomIt>::value_type>::value>::type >
void CountingSortInt(RandomIt begin, RandomIt end) {
    using ValueType = typename std::iterator_traits<RandomIt>::value_type;
    size_t max = *std::max_element(begin, end);
    std::vector<ValueType> count;
    count.resize(max+1);
    for ( auto value=begin; value!=end ;++value){
        ++count[*value];
    }
    size_t counter=-1;
    for (auto it=count.begin(); it!=count.end() ;++it){
        ++counter;
        ValueType value = counter;
        size_t size = *it;
        if(size==0){
            continue;
        }
        std::fill_n(begin, size, value);
        std::advance(begin, size);
    }
}

template<typename RandomIt,class = typename std::enable_if<!std::is_integral<typename std::iterator_traits<RandomIt>::value_type>::value>::type >
void CountingSortNonInt(RandomIt begin, RandomIt end) {
    using ValueType = typename std::iterator_traits<RandomIt>::value_type;
    std::map<ValueType, std::size_t> counts;

    for (auto value = begin; value != end; ++value) {
        ++counts[*value];
    }

    for (auto &count: counts) {
        ValueType value = count.first;
        size_t size = count.second;
        std::fill_n(begin, size, value);
        std::advance(begin, size);
    }
}

struct person {
    std::string name;
    int age;
};

bool operator<(const person &lhs, const person &rhs) {
    return lhs.age < rhs.age;
}

bool operator>(const person &lhs, const person &rhs) {
    return lhs.age > rhs.age;
}

bool operator==(const person &lhs, const person &rhs) {
    return lhs.age == rhs.age;
}

void RunSortTestExample() {
    vector<int> vector1 = {1, 5, 7, 82, 3, 5, 7, 12};
    InsertionSort(vector1.begin(), vector1.end());
    for (auto x:vector1) {
        std::cout << x << " ";
    }
    std::cout << std::endl;
    int array[] = {1, 5, 72, 3, 42, 45, 2, 35, 6};
    InsertionSort(std::begin(array), std::end(array));
    for (auto x:array) {
        std::cout << x << " ";
    }
    std::cout << std::endl;
    vector<person> persons = {
            {
                    "ilya",
                    18,
            },
            {
                    "egor",
                    19,
            },
            {
                    "yana",
                    22,
            },
            {
                    "andrei",
                    20,
            }

    };
    InsertionSort(persons.begin(), persons.end());
    for (const auto&[name, age]:persons) {
        std::cout << name << " " << age << std::endl;
    }
    std::cout<<std::endl;
}

void RunCountingSortTestExample() {
    vector<int> vector1 = {1, 5, 7, 82, 3, 5, 7, 12};
    CountingSortInt(vector1.begin(), vector1.end());
    for (auto x:vector1) {
        std::cout << x << " ";
    }
    std::cout << std::endl;
     int array[] = {1, 5, 72, 3, 42, 45, 2, 35, 6};
    CountingSortInt(std::begin(array), std::end(array));
     for (auto x:array) {
         std::cout << x << " ";
     }
     std::cout << std::endl;
     vector<person> persons = {
             {
                     "ilya",
                     18,
             },
             {
                     "egor",
                     19,
             },
             {
                     "yana",
                     22,
             },
             {
                     "andrei",
                     20,
             }

     };
     CountingSortNonInt(persons.begin(), persons.end());
     for (const auto&[name, age]:persons) {
         std::cout << name << " " << age << std::endl;
     }
}

int main() {
     RunSortTestExample();
    RunCountingSortTestExample();
    return 0;
}