# Merge Sort

Oct 20th, 2021 (edited)
715
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #include <bits/stdc++.h>
2. #define ll long long int
3. #define ull unsigned long long int
4. #define pb push_back
5. #define mp make_pair
6. #define in insert
7. #define f first
8. #define sc second
9. #define M 1000000
10. #define MAX 1000010
11. using namespace std;
12.
13. void merge(int lb,int ub,int a[],int mid,int n)
14. {
15.   int i = lb,j = mid+1,k = lb,b[n];
16.   while(i<=mid && j<=ub)
17.   {
18.     if(a[i]<=a[j]){b[k] = a[i];i++;k++;}
19.     else {b[k] = a[j];j++;k++;}
20.   }
21.   if(i>mid)
22.   {
23.     while(j<=ub){b[k] = a[j];k++;j++;}
24.   }
25.   else
26.   {
27.     while(i<=mid){b[k] = a[i];i++;k++;}
28.   }
29.
30.   for(i=lb;i<=ub;i++) a[i] = b[i];
31. }
32. void mergeSort(int lb,int ub,int a[],int n)
33. {
34.   int mid;
35.   if(lb<ub)
36.   {
37.     mid = (lb+ub)/2;
38.     mergeSort(lb,mid,a,n);
39.     mergeSort(mid+1,ub,a,n);
40.     merge(lb,ub,a,mid,n);
41.   }
42. }
43.
44. int main()
45. {
46.   int n;
47.   cin >> n;
48.   int a[n];
49.   for(int i=0;i<n;i++) cin >> a[i];
50.   cout << "Before sorting:" << endl;
51.   for(int i=0;i<n;i++) cout << a[i] << " ";
52.   cout << endl << endl;
53.   mergeSort(0,n-1,a,n);
54.   cout << "After sorting:" << endl;
55.   for(int i=0;i<n;i++) cout << a[i] << " ";
56.
57.   return 0;
58. }
59.
RAW Paste Data