Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
1.4 kB
4
Indexable
Never
#include <iostream>

void merge (int* massive, int start, int middle, int end, long int& count){
    int it1 = 0;
    int it2 = 0;
    int result[end - start];
    while (start + it1 < middle && middle + it2 < end){
        if (massive[start + it1] <= massive[middle + it2]) {
            result[it1 + it2] = massive[start + it1];
            ++it1;
        }else{
            result[it1 + it2] = massive[middle + it2];
            count += middle - it1;
            ++it2;
        }
    }
    while (start + it1 < middle){
        result[it1 + it2] = massive[start + it1];
        ++it1;
    }
    while (middle + it2 < end){
        result[it1 + it2] = massive[middle + it2];
        ++it2;
    }
    for (int i = 0; i < it1+it2; i++){
        massive[start+i] = result[i];
    }
}

void MergeSort (int* massive, int start, int end, long int& count) {
    if (start + 1 >= end){
        return;
    }
    int middle = (end + start) / 2;
    MergeSort(massive, start, middle, count);
    MergeSort(massive, middle, end, count);
    merge(massive, start, middle, end, count);
}
int main() {
    int length;
    long int wrong_count = 0;
    std::cin >> length;
    int massive[length];
    for (int i = 0; i < length; i++){
        std::cin >> massive[i];
    }
    MergeSort(massive, 0, length, wrong_count);
    std::cout << wrong_count / 2;
}