This repository has been archived by the owner on Oct 29, 2023. It is now read-only.
-
Notifications
You must be signed in to change notification settings - Fork 769
/
Bhargav1
83 lines (68 loc) · 1.86 KB
/
Bhargav1
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
81
82
83
#include <iostream>
#include <vector>
using namespace std;
// Merge two subarrays of vector 'arr'.
// First subarray is arr[l..m]
// Second subarray is arr[m+1..r]
void merge(vector<int>& arr, int l, int m, int r) {
int n1 = m - l + 1;
int n2 = r - m;
// Create temporary vectors
vector<int> L(n1);
vector<int> R(n2);
// Copy data to temporary vectors L[] and R[]
for (int i = 0; i < n1; i++)
L[i] = arr[l + i];
for (int j = 0; j < n2; j++)
R[j] = arr[m + 1 + j];
// Merge the temporary vectors back into arr[l..r]
int i = 0, j = 0, k = l;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
// Copy the remaining elements of L[], if there are any
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
// Copy the remaining elements of R[], if there are any
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
// l is for left index and r is for right index of the sub-vector of arr to be sorted
void mergeSort(vector<int>& arr, int l, int r) {
if (l < r) {
int m = l + (r - l) / 2; // Same as (l+r)/2, but avoids overflow for large l and r
// Sort first and second halves
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
// Merge the sorted halves
merge(arr, l, m, r);
}
}
int main() {
vector<int> arr = {12, 11, 13, 5, 6, 7};
int arr_size = arr.size();
cout << "Given array is: ";
for (int i = 0; i < arr_size; i++)
cout << arr[i] << " ";
cout << endl;
// Perform merge sort
mergeSort(arr, 0, arr_size - 1);
cout << "Sorted array is: ";
for (int i = 0; i < arr_size; i++)
cout << arr[i] << " ";
cout << endl;
return 0;
}