Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <fstream>
- using namespace std;
- int merge(int a[], int first, int m, int last, int n){
- int amt = 0;
- int l = first;
- int r = last;
- int k = first;
- int *b = new int [n];
- while ((l <= m - 1) && (r <= last)){
- if (a[l] <= a[r]){
- b[k] = a[l];
- k++;
- l++;
- }
- else{
- b[k] = a[r];
- k++;
- r++;
- amt = amt + (m - l);
- }
- }
- while (l <= m - 1) {
- b[k] = a[l];
- k++;
- l++;
- }
- while (r <= last) {
- b[k] = a[r];
- k++;
- r++;
- }
- for(int i = 0; i < last; i++){
- a[i] = b[i];
- }
- return amt;
- }
- int mergesort(int a[], int first, int last, int n){
- int m = (first + last)/2;
- int amt = 0;
- if (first < last){
- amt = mergesort(a, first, m, n);
- amt += mergesort(a, m + 1, last, n);
- amt += merge(a, first, m + 1, last, n);
- }
- return amt;
- }
- int main() {
- ifstream fin("input.txt");
- ofstream fout("output.txt");
- int n;
- fin >> n;
- int *a = new int [n];
- for(int i = 0; i < n; i++){
- fin >> a[i];
- }
- fout << mergesort(a, 0, n - 1, n);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement