-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathTestMergeSort.cpp
74 lines (56 loc) · 1.32 KB
/
TestMergeSort.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
72
73
74
#include<iostream>
using namespace std;
void merge(int arr[],int start,int mid,int stop){
int n1 = mid - start + 1;
int m1 = stop - mid;
int arr2[n1],arr3[m1];
//keep layer array
for(int i = 0 ; i < n1 ; i++){ arr2[i] = arr[i+start];}
for(int i = 0 ; i < m1 ; i++){ arr3[i] = arr[i+mid+1];}
//start compare
int i,j,k;
i = j = 0;
k = start;
while(i < n1 && j < m1){
if(arr2[i] <= arr3[j]){
arr[k] = arr2[i];
i++;
}else{
arr[k] = arr3[j];
j++;
}
k++;
}
//leftover
while(i < n1){
arr[k] = arr2[i];
i++; k++;
}
while(j < m1){
arr[k] = arr3[j];
j++; k++;
}
}
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++)
cout << arr[i] << " ";
cout << endl;
}
void mergesort(int arr[],int start,int stop){
if(start < stop){
int m = (start+stop)/2; //trim down
mergesort(arr,start,m);
mergesort(arr,m+1,stop);
//go furthest down before starting calculating
merge(arr,start,m,stop);
}
}
// Driver program
int main() {
int arr[] = {6, 5, 12, 10, 9, 1};
int size = sizeof(arr) / sizeof(arr[0]);
mergesort(arr, 0, size - 1);
cout << "Sorted array: \n";
printArray(arr, size);
return 0;
}