-
Notifications
You must be signed in to change notification settings - Fork 0
/
MergeSort.java
125 lines (96 loc) · 2.94 KB
/
MergeSort.java
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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
/*
Sort a given set of n integer elements using Merge Sort method and compute its time
complexity. Run the program for varied values of n> 5000, and record the time taken to sort.
Plot a graph of the time taken versus non graph sheet. The elements can be read from a file or
can be generated using the random number generator. Demonstrate using Java how the divide-
and-conquer method works along with its time complexity analysis: worst case, average case
and best case.
*/
import java.io.*;
import java.util.*;
class MergeSort
{
public static void main(String args[])
{
Scanner s=new Scanner(System.in);
Random r=new Random();
//Input number of elements
System.out.println("Enter no of elements :");
int n=s.nextInt();
int arr[]=new int[n];
//Initialize array with random numbers
for(int i=0;i<n;i++)
arr[i]=r.nextInt();
MergeSort sorter=new MergeSort();
//log time before and after sorting
long start_time=System.nanoTime();
arr=sorter.divide(0,n-1,arr);
long end_time=System.nanoTime();
//Display Sorted array and time taken for sorting.
System.out.println("Sorted array is :\n"+Arrays.toString(arr));
System.out.println("Time for sorting is : "+ (end_time - start_time)/1000000.0+" ms");
}
//l=left most (low) , r=right most(high)
int[] divide(int l,int r,int arr[])
{
int m;//m=mid element index
//Perfrom recursion until 1 element is left as arr
if(l<r)
{
//calculate mid as (low+high)/2
m=(l+r)/2;
//recursively divide first sub arr
divide(l,m,arr);
//recursively divide second sub arr
divide(m+1,r,arr);
//Merge all the sub arrays into arr
merge(l,m,r,arr);
}
//Return sorted array
return arr;
}
void merge(int l,int m,int r,int arr[])
{
int n1=m-l+1;//here we calculate size hence we need to do +1 to account for array index starting from 0
int n2=r-m;
//create arrays of sizes n1 and n2
int left_arr[]=new int[n1];
int right_arr[]=new int[n2];
//Copy the data from arr to left_arr and right_arr respectively
int x=0;
for(int i=l;i<=m;i++)
{ left_arr[x]=arr[i];
x++;
}
x=0;
for(int i=m+1;i<=r;i++)
{ right_arr[x]=arr[i];
x++;
}
//i is a pointer to left_arr, j to right_arr and k to 'main' arr[]
int i=0,j=0,k=l;//**NOTE** access arr[] from l'th index ,hence k=l
//While either of the arrays have not been fully traversed
while(i<n1 && j<n2)
{
//Pick the smaller element between left_arr[i] or right_arr[j] and then add to arr[k]
if(left_arr[i]<right_arr[j])
{ arr[k]=left_arr[i];
i++;k++;
}
else
{ arr[k]=right_arr[j];
j++;k++;
}
}
//After either of the arrays have completed traversing empty the remain contents of either left or right arrays into arr.
//**NOTE** Only one of the below 2 loops will run,because either i==n1 or j==n2 for the above while-loop to break
while(i<n1)
{ arr[k]=left_arr[i];
i++;k++;
}
while(j<n2)
{ arr[k]=right_arr[j];
j++;k++;
}
}
}