# Merge Sort

Feb 2nd, 2023
604
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #include<bits/stdc++.h>
2. #define endl "\n"
3.
4. using namespace std;
5.
6. void merge_them(vector<int> &ara, int L, int mid, int R) {
7.     vector<int> partial_sort;
8.     int L1 = L, R1 = mid, L2 = mid + 1, R2 = R;
9.
10.     while(L1<=R1 && L2<=R2) {
11.         if(ara[L1] <= ara[L2]) {
12.             partial_sort.push_back(ara[L1]);
13.             L1++;
14.         } else {
15.             partial_sort.push_back(ara[L2]);
16.             L2++;
17.         }
18.     }
19.     while(L1<=R1) {
20.         partial_sort.push_back(ara[L1]);
21.         L1++;
22.     }
23.     while(L2<=R2) {
24.         partial_sort.push_back(ara[L2]);
25.         L2++;
26.     }
27.     for(int i = 0, j = L; i<partial_sort.size(); i++, j++) {
28.         ara[j] = partial_sort[i];
29.     }
30. }
31.
32. void merge_sort(vector<int>&arr, int L, int R) {
33.     if (L >= R) return;
34.     int M = (L + R) / 2;
35.
36.     /// arr -> [6, 2, 5, 11, 1, -1, 7, 3]
37.
38.     merge_sort(arr, L, M);
39.     /// arr[L,...,M] is sorted. arr -> [2, 5, 6, 11, 1, -1, 7, 3]
40.
41.     merge_sort(arr, M + 1, R);
42.     /// arr[M + 1,...,R] is sorted. arr -> [2, 5, 6, 11, -1, 1, 3, 7]
43.
44.     merge_them(arr, L, M, R);
45.     /// arr[L,...,R] -> [-1, 1, 2, 3, 5, 6, 7, 11]
46. }
47.
48. void merge_sort(vector<int>&arr) {
49.     merge_sort(arr, 0, arr.size() - 1);
50. }
51.
52. int main()
53. {
54.     int n;
55.     cin >> n;
56.     vector<int> arr(n);
57.     for (int i = 0; i < n; i++)
58.     {
59.         cin >> arr[i];
60.     }
61.     merge_sort(arr);
62.     if (is_sorted(arr.begin(), arr.end())) {
63.         cout << "SUCCESS\n";
64.     }
65.     else {
66.         cout << "FAILURE\n";
67.     }
68.     return 0;
69. }