counting_inversion.cpp

#include <iostream>
#include <fstream>
#include <vector>

const std::string KFILE_NAME = "./intlist.txt";
static long long inverse_counter = 0;

template <class VecIter>
auto  merge(VecIter iter_begin, VecIter iter_middle, VecIter iter_end){
    size_t iter_dis = std::distance(iter_begin, iter_end);

    using IterType = typename std::iterator_traits<VecIter>::value_type;
    std::vector<IterType> buf;
    buf.reserve(iter_dis);
    VecIter l_iter = iter_begin, r_iter = iter_middle;
    while(l_iter != iter_middle && r_iter != iter_end){
        if (*l_iter < *r_iter) {
            buf.push_back(*l_iter);
            l_iter++;
        } else {
            buf.push_back(*r_iter);
            r_iter++;
            inverse_counter += std::distance(l_iter, iter_middle);
        }
    }
    while(l_iter != iter_middle){
        buf.push_back(*l_iter);
        l_iter++;
    }
    while(r_iter != iter_end){
        buf.push_back(*r_iter);
        r_iter++;
    }
    return buf;
}
template <class VecIter>
void mergesort(VecIter iter_begin, VecIter iter_end) {
    using IterType = typename std::iterator_traits<VecIter>::value_type;
    std::size_t iter_dis = std::distance(iter_begin, iter_end);
    if (iter_begin == std::prev(iter_end)) {
        return;
    }
    std::size_t middle = iter_dis / 2;
    VecIter iter_middle = iter_begin;
    std::advance(iter_middle, middle);

    mergesort(iter_begin, iter_middle);
    mergesort(iter_middle, iter_end);

    std::vector<IterType> buf = merge(iter_begin, iter_middle, iter_end);
    std::move(buf.begin(), buf.end(), iter_begin);
}
int main() {
    std::ifstream fp(KFILE_NAME);
    if (!fp.is_open()) {
        std::cout << "file not opend\n";
        return 0;
    }
    std::string buf;
    std::vector<int> numvec;
    numvec.reserve(10000);

    int cnt = 0;
    while(!std::getline(fp, buf).eof()) {
        int int_buf = std::stoi(buf);
        numvec.push_back(int_buf);
        ++cnt;
    }
    fp.close();
    std::cout << cnt << std::endl;

    std::cout << "sort\n";
    mergesort(numvec.begin(), numvec.end());
    int before_num = 0;
    for (int num : numvec) {
        if (before_num > num) {
            std::cout << "not sorted\n";
            return -1;
        }
        before_num = num;
    }
    std::cout << "counted inverse : " << inverse_counter << std::endl;
    return 0;
}