Untitled
unknown
plain_text
2 years ago
1.4 kB
12
Indexable
#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;
}Editor is loading...