1. #include <iostream>
2. #include <algorithm>
3. #include <vector>
4. #include <chrono>
5. using namespace std;
6.  
7. void merge(vector<int> a, int p, int q, int r) {
8.   //defining well named variables
9.   int range = r - p + 1;
10.  
11.   int lowHalf = q - p + 1;
12.   int highHalf = r - q;
13.  
14.   int rStart = q + 1;
15.   int rEnd = r;
16.   int lStart = p;
17.   int lEnd = q;
18.  
19.   //filling temp array
20.   std::vector<int> temp;
21.   for (int i = 0; i < range; i++) {
22.     temp.push_back(a[lStart + i]);
23.   }
24.  
25.   //mergin subarrays
26.   int left = lStart;
27.   int right = rStart;
28.   int k = 0; //index
29.   while( (left <= lEnd) && (right <= rEnd)) {
30.     if(a[left] <= a[right]) {
31.       temp[k] = a[left];
32.       left++;
33.     } else {
34.       temp[k] = a[right];
35.       right++;
36.     }
37.     k++;
38.   }
39.  
40.   //coping rest of subarrays
41.   while (right <= rEnd) {temp[k++] = a[right++];}
42.   while (left <= rEnd) {temp[k++] = a[left++];}
43.  
44.   //coping temp array to origin
45.   for (int i = 0; i < range; i++) {
46.     a[lStart + i] = temp[i];
47.   }
48.  
49. }
50. void mergeSortRec(vector<int> arr, int l, int r) {
51.   int p;
52.   if(l < r) {
53.     p = (l+r)/2;
54.     mergeSortRec(arr, l, p);
55.     mergeSortRec(arr, p+1, r);
56.     merge(arr, l,p, r);
57.   }
58. }
59.  
60. void mergeSortIter(vector<int> arr, int l, int r) {
61.   int n = r - l - 1;
62.   int size;
63.   int start;
64.  
65.   for (size = 1; size <= n; size *= 2) {
66.     for (start = 0; start < n; start += 2*size) {
67.       //index of left end
68.       int mid = start + size - 1;
69.       //are we out of the bound?
70.       int end = min(start + 2*size - 1, n);
71.  
72.       merge(arr, start, mid, end);
73.     }
74.   }
75. }
76.  
77. void merge_sort_time(vector<int> v) {
78.   auto start = chrono::high_resolution_clock::now();
79.   mergeSortRec(v,0,v.size()-1);
80.   auto end = chrono::high_resolution_clock::now();
81.   chrono::duration<double> elapsed = end - start;
82.   std::cout << elapsed.count() << endl;
83. }
84.  
85. auto main(int argc, char const *argv[]) -> int
86. {
87.   ios_base::sync_with_stdio(false);
88.   int x;
89.   vector<int> v;
90.  
91.   // getting inputs
92.   while(cin >> x)
93.   {
94.     v.push_back(x);
95.     cin.clear();
96.     cin.sync();
97.     std::cout << "One" << '\n';
98.   }
99.   // vector<int> sorted = selection_sort(v);
100.   // printVector(sorted);
101.   merge_sort_time(v);
102. }
103.