Advertisement
sherry_ahmos

Merge sort

Dec 25th, 2022 (edited)
1,000
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.34 KB | None | 0 0
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. void sherry()
  5. {
  6.     ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  7. #ifndef ONLINE_JUDGE
  8.     freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout);
  9. #endif
  10. }
  11.  
  12. void merg(int arr[], int l, int m, int r)
  13. {
  14.     int i, j, k = l;
  15.     int n1 = m - l + 1, n2 = r - m;
  16.     int L[n1], R[n2];
  17.     for (int i = 0; i < n1; i++)
  18.         L[i] = arr[l + i];
  19.     for (int i = 0; i < n2; i++)
  20.         R[i] = arr[m + i + 1];
  21.     i = j = 0;
  22.     while (i < n1 and j < n2)
  23.     {
  24.         if (L[i] < R[j])
  25.         {
  26.             arr[k] = L[i];
  27.             i++;
  28.         }
  29.         else
  30.         {
  31.             arr[k] = R[j];
  32.             j++;
  33.         }
  34.         k++;
  35.     }
  36.     while (i < n1)
  37.     {
  38.         arr[k] = L[i];
  39.         i++, k++;
  40.     }
  41.     while (j < n2)
  42.     {
  43.         arr[k] = R[j];
  44.         j++, k++;
  45.     }
  46. }
  47. void mergeSort(int arr[], int l, int r)
  48. {
  49.     if (l < r)
  50.     {
  51.         int m = (l + r) / 2;
  52.         mergeSort(arr, l, m);
  53.         mergeSort(arr, m + 1, r);
  54.         merg(arr, l, m, r);
  55.     }
  56. }
  57. int main()
  58. {
  59.     sherry();
  60.     ll n;
  61.     cin >> n;
  62.     int arr[n];
  63.     for (int i = 0; i < n; i++)
  64.     {
  65.         cin >> arr[i];
  66.     }
  67.     mergeSort(arr, 0, n - 1);
  68.     for (int i = 0; i < n; i++)
  69.         cout << arr[i] << " ";
  70.     return 0;
  71. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement