#include <iostream> #include "message.h" #include "teatr.h" using namespace std; long long merge(int arr[], int temp[], int left, int mid, int right) { int i, j, k; long long inv_count = 0; i = left; j = mid; k = left; while((i <= mid - 1) && (j <= right)) { if(arr[i] <= arr[j]) { temp[k++] = arr[i++]; } else { temp[k++] = arr[j++]; inv_count = inv_count + (mid - i); } } while(i <= mid - 1) { temp[k++] = arr[i++]; } while(j <= right) { temp[k++] = arr[j++]; } for(i = left; i <= right; i++) { arr[i] = temp[i]; } return inv_count; } long long mergeSort(int arr[], int temp[], int left, int right) { int mid; long long inv_count = 0; if(right > left) { mid = (right + left) / 2; inv_count = mergeSort(arr, temp, left, mid); inv_count += mergeSort(arr, temp, mid + 1, right); inv_count += merge(arr, temp, left, mid + 1, right); } return inv_count; } int main() { if(MyNodeId() == 0) { int n = GetN(), i; int* t = new int[n]; int* temp = new int[n]; for(i = 0; i < n; i++) { t[i] = GetElement(i); } cout << mergeSort(t, temp, 0, n - 1) << "\n"; } return 0; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 | #include <iostream> #include "message.h" #include "teatr.h" using namespace std; long long merge(int arr[], int temp[], int left, int mid, int right) { int i, j, k; long long inv_count = 0; i = left; j = mid; k = left; while((i <= mid - 1) && (j <= right)) { if(arr[i] <= arr[j]) { temp[k++] = arr[i++]; } else { temp[k++] = arr[j++]; inv_count = inv_count + (mid - i); } } while(i <= mid - 1) { temp[k++] = arr[i++]; } while(j <= right) { temp[k++] = arr[j++]; } for(i = left; i <= right; i++) { arr[i] = temp[i]; } return inv_count; } long long mergeSort(int arr[], int temp[], int left, int right) { int mid; long long inv_count = 0; if(right > left) { mid = (right + left) / 2; inv_count = mergeSort(arr, temp, left, mid); inv_count += mergeSort(arr, temp, mid + 1, right); inv_count += merge(arr, temp, left, mid + 1, right); } return inv_count; } int main() { if(MyNodeId() == 0) { int n = GetN(), i; int* t = new int[n]; int* temp = new int[n]; for(i = 0; i < n; i++) { t[i] = GetElement(i); } cout << mergeSort(t, temp, 0, n - 1) << "\n"; } return 0; } |