-
Notifications
You must be signed in to change notification settings - Fork 0
/
MergeSort.java
73 lines (65 loc) · 2.03 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
public class MergeSort {
int array[];
int size;
public MergeSort(int n) {
size=n;
//create array with size n
array=new int[n];
//asign value into the array
for (int i=0;i<n;i++){
array[i]=(int) Math.round(Math.random()*89+10);
}
}
public int getSize() {
return size;
}
public void merge(int left, int mid, int right) {
int temp [] =new int[right-left+1];
int i = left;
int j = mid+1;
int k = 0;
while (i <= mid && j <= right) {
if (array[i] <= array[j]) {
temp[k] = array[i];
k++;
i++;
} else { //array[i]>array[j]
temp[k] = array[j];
k++;
j++;
}
}
while(j<=right) temp[k++]=array[j++];
while(i<=mid) temp[k++]=array[i++];
for(k=0;k<temp.length;k++) array[left+k]=temp[k];
}
public void merge_sort(int left,int right){
// Check if low is smaller then high, if not then the array is sorted
if(left<right){
// Get the index of the element which is in the middle
int mid=(left+right)/2;
// Sort the left side of the array
merge_sort(left,mid);
// Sort the right side of the array
merge_sort(mid+1,right);
// Combine them both
merge(left,mid,right);
}
}
public void print(){
System.out.println("Contents of the Array");
for(int k=0;k<15;k++) {
System.out.print(array[k]+" | ");
}
System.out.println();
}
public static void main(String args[]){
MergeSort m=new MergeSort(15);
System.out.println("Before Sort <<<<<<<<<<<<<<<<<<<<<");
m.print();
m.merge_sort(0,m.getSize()-1);
System.out.println("After Sort > > > > > > > > > > > >");
m.print();
System.out.println("=======+============+=======+============+=========");
}
}