forked from AbdulMoghni/Hacker-rank-solution
-
Notifications
You must be signed in to change notification settings - Fork 0
/
mergeSort.cpp
71 lines (68 loc) · 1.16 KB
/
mergeSort.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <iostream>
#include <vector>
using namespace std;
vector<int> Merge(vector<int> L, vector<int> R){
vector<int> A;
int Ls=L.size();
int Rs=R.size();
int As=Ls+Rs;
int Li=0;
int Ri=0;
int Ai=0;
while(Ai<As){
if(Li<Ls && Ri<Rs){
if(L[Li]<=R[Ri]){
A.push_back(L[Li]);
Li++;
}
else{
A.push_back(R[Ri]);
Ri++;
}
}
else{
if(Ri<Rs){
A.push_back(R[Ri]);
Ri++;
}
else if(Li<Ls){
A.push_back(L[Li]);
Li++;
}
}
Ai++;
}
return A;
}
vector<int> MergeSort(vector<int>& V, int beg, int end){
if(beg>end){
vector<int> ansV;
return ansV;
}
if(beg==end){
vector<int> ansV;
ansV.push_back(V[end]);
return ansV;
}
int m=(beg+end)/2;
vector<int> Ls=MergeSort(V, beg, m);
vector<int> Rs=MergeSort(V, m+1, end);
return Merge(Ls, Rs);
}
int main(){
cout<<"Enter number of integers to sort: \n";
int n;
cin>>n;
vector<int> V;
cout<<"Enter the integers: \n";
for(int i=0; i<n; i++){
int x;
cin>>x;
V.push_back(x);
}
vector<int> sorted=MergeSort(V, 0, n-1);
cout<<"Sorted integers are: \n";
for(int i =0;i<sorted.size();i++)
cout<<sorted[i]<<" ";
cout<<endl;
}