SHARE
TWEET

Untitled

a guest Oct 9th, 2019 103 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <fstream>
  3. #include <vector>
  4. #include <cmath>
  5. using namespace std;
  6.  
  7.  
  8. void mergeSort(vector<int>& a, int start, int end)
  9. {
  10.     if (start + 1 >= end)
  11.     {
  12.         return;
  13.     }
  14.     mergeSort(a, start, start + (end - start) / 2);
  15.     mergeSort(a, start + (end - start) / 2, end);
  16.    
  17.     vector<int> b;
  18.     int b1 = start;
  19.     int e1 = start + (end - start) / 2;
  20.    
  21.     int b2 = start + (end - start) / 2;
  22.     int e2 = end;
  23.     while (b.size() < end - start)
  24.     {
  25.         if (b1 == e1 || (b2 < e2 && a[b2] < a[b1]))
  26.         {
  27.             b.push_back(a[b2]);
  28.             b2++;
  29.         }
  30.         else
  31.         {
  32.             b.push_back(a[b1]);
  33.             b1++;
  34.         }
  35.     }
  36.     for (int i = start; i < end; i++)
  37.     {
  38.         a[i] = b[i-start];
  39.     }
  40. }
  41.  
  42. int main()
  43. {
  44.     srand(time(0));
  45.     ifstream fin("sort.in");
  46.     ofstream fout("sort.out");
  47.  
  48.     int n = 0;
  49.     cin >> n;
  50.     vector<int> v;
  51.     v.resize(n);
  52.     for (int i = 0; i < n; ++i)
  53.     {
  54.         cin >> v[i];
  55.     }
  56.     mergeSort(v, 0, n);
  57.  
  58.     for (int i = 0;i<n;i++)
  59.         cout << v[i] << " ";
  60.     fin.close();
  61.     fout.close();
  62. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top