Advertisement
pedrocasdev

Mergesort Count inversion

Sep 17th, 2022
95
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.84 KB | None | 0 0
  1. int merge(int arr[], int l, int m, int r)
  2. {
  3.     int count = 0;
  4.     int i, j, k;
  5.     int n1 = m - l + 1;
  6.     int n2 = r - m;
  7.     int L[n1], R[n2];
  8.  
  9.     for (i = 0; i < n1; i++)
  10.         L[i] = arr[l + i];
  11.     for (j = 0; j < n2; j++)
  12.         R[j] = arr[m + 1 + j];
  13.  
  14.  
  15.     i = 0;
  16.     j = 0;
  17.     k = l;
  18.     while (i < n1 && j < n2) {
  19.         if (L[i] <= R[j]) {
  20.             arr[k] = L[i];
  21.             i++;
  22.         }
  23.         else {
  24.             arr[k] = R[j];
  25.             j++;
  26.        
  27.         count += (n1 - i);
  28.         }
  29.         k++;
  30.     }
  31.  
  32.  
  33.     while (i < n1) {
  34.         arr[k] = L[i];
  35.         i++;
  36.         k++;
  37.     }
  38.  
  39.  
  40.     while (j < n2) {
  41.         arr[k] = R[j];
  42.         j++;
  43.         k++;
  44.     }
  45. return count;
  46. }
  47.  
  48. int mergeSort(int arr[], int l, int r)
  49. {
  50.     int count = 0;
  51.     if (l < r) {
  52.         int m = l + (r - l) / 2;
  53.  
  54.         count+=mergeSort(arr, l, m);
  55.         count+=mergeSort(arr, m + 1, r);
  56.  
  57.         count+=merge(arr, l, m, r);
  58.          
  59.     }
  60.     return count;
  61. }
  62.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement