-
Notifications
You must be signed in to change notification settings - Fork 2
/
mergesort.cpp
100 lines (80 loc) · 1.65 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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#include <iostream>
#include <ctime>
#include <stdlib.h>
using namespace std;
//merge algorithm
void merge(int a[], int low, int middle, int high)
{
int i,j,k;
int b[500000];
i=low; k=low; j=middle+1;
//compare the two arrays
//and keep adding the smaller
//element in a new array
while(i<=middle && j<=high)
{
if(a[i]<=a[j])
b[k++] = a[i++];
else
b[k++] = a[j++];
}
//if elements in any one array is over
//copy the remaining elements in the
//other array in the new array
while(i<=middle)
b[k++]=a[i++];
while(j<=high)
b[k++]=a[j++];
//Now copy the new array back
//to the original array
for(k=0; k<=high; k++)
a[k] = b[k];
}
void mergesort(int a[], int low, int high)
{
int middle;
if(low<high)
{
middle = (low+high)/2; //find the middle element
mergesort(a,low,middle); // Apply mergesort to first half of array
mergesort(a,middle+1,high); // Apply mergesort to second half of array
merge(a,low,middle,high); //Merge the two halves
}
}
void getElements(int a[], int size)
{
for(int i=0; i<size; i++)
{
a[i] = rand()%100; // Random numbers 0-99
}
}
void display(int a[], int size)
{
for (int i=0; i<size; i++)
{
cout<<a[i]<<" ";
}
cout<<endl;
}
int main()
{
int a[500000];
int low, middle, high;
int size;
clock_t start,end;
double totaltime;
cout<<"Enter array size: ";
cin>>size;
getElements(a,size);
// cout<<"Unsorted array: "<<endl;
// display(a,size);
start = clock();
mergesort(a,0,size-1);
end = clock();
// cout<<"Sorted array: "<<endl;
// display(a,size);
totaltime = (double)(end-start)/(CLOCKS_PER_SEC);
cout<<endl;
cout<<"The time taken is " <<totaltime<< endl;
return 0;
}