-
Notifications
You must be signed in to change notification settings - Fork 0
/
merge-sort-vector.cc
88 lines (59 loc) · 1.7 KB
/
merge-sort-vector.cc
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
84
85
86
87
88
#include <iostream>
#include <math.h>
#include <vector>
using std::cin;
using std::cout;
using std::endl;
using std::boolalpha;
using std::floor;
using std::vector;
void merge_sort(vector<int> &list, size_t s_index, size_t l_index);
void merge(vector<int> &list, size_t s_index, size_t middle, size_t l_index);
int main (){
cout << boolalpha;
vector<int> arr_list {7,1,3,0,9,2,4,5};
cout << "list before sorting : ";
for (auto const &item: arr_list){
cout << item << " " ;
}
cout << "\n list after sorting : ";
merge_sort(arr_list,0,7);
for(auto const &item: arr_list){
cout << item << " ";
}
cout << "" << endl;
return 0;
}
void merge(vector<int> &list, size_t s_index, size_t middle, size_t l_index){
size_t n1{middle - s_index + 1};
size_t n2{l_index - middle};
vector<int> L (n1+1);
vector<int> R (n2+1);
for(size_t i {0}; i < n1; i ++){
L.at(i) = list.at(s_index + i);
}
for(size_t j {0}; j < n2; j ++){
R.at(j) = list.at(middle + j + 1);
}
L.at(n1) = static_cast<int>(MAXFLOAT);
R.at(n2) = static_cast<int>(MAXFLOAT);
size_t i {0};
size_t j {0};
for(size_t k {s_index}; k <= l_index; k++){
if(L.at(i) <= R.at(j)){
list.at(k) = L.at(i);
i++;
}else{
list.at(k) = R.at(j);
j++;
}
}
}
void merge_sort(vector<int> &list, size_t s_index, size_t l_index){
if(s_index < l_index){
size_t middle {static_cast<size_t>(floor((s_index + l_index)/2))};
merge_sort(list, s_index, middle);
merge_sort(list, middle + 1, l_index);
merge(list,s_index,middle,l_index);
}
}