Algorithms/MergeSort.cpp at master · AnkithReddy02/Algorithms · GitHub

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
72
73
74
75
76
77
78
79
80
#include<bits/stdc++.h>

using namespace std;

ostream& operator << (ostream& cout, vector<int> & a) {
	for(int & x : a) {
		cout << x << ' ';
	}

	cout << endl;
}


void merge(vector<int> & a, int l1, int r1, int l2, int r2) {

	int l = l1;
	int r = r2;
	vector<int> res;
	while(l1 <= r1 && l2 <= r2) {
		if(a[l1] < a[l2]) {
			res.push_back(a[l1++]);
		}
		else {
			res.push_back(a[l2++]);
		}
	}

	while(l1 <= r1) {
		res.push_back(a[l1++]);
	}

	while(l2 <= r2) {
		res.push_back(a[l2++]);
	}

	for(int & x : res) {
		a[l++] = x;
	}


	return;
}
void mergesort(vector<int> & a, int low, int high) {

	if(low == high) {
		return;
	}
	if(low < high) {
		int mid = (low + high + 1)/2;


		mergesort(a, low, mid-1);
		mergesort(a, mid, high);

		merge(a, low, mid - 1, mid, high);

	}


	return;
}
int main() {

	int n;

	cin >> n;

	vector<int> a(n);

	for(int i=0;i<n;i++) {

		a[i] = rand()%1000;
	}


	mergesort(a, 0, a.size() - 1);

	cout << a << endl;
}