Untitled
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; }