-
Notifications
You must be signed in to change notification settings - Fork 4
/
MergeSort.java
155 lines (136 loc) · 3.5 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
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
package sort.merge;
import java.lang.reflect.Array;
import java.util.Arrays;
import sort.AbstractBase;
/**
* @author Suyash
* <p>Complexity in worst case is <b>O(nlog(n))</b>.</p>
*/
public class MergeSort extends AbstractBase {
/*
array[] = {5, 7, 1, 4, 2, 9, 3}
*/
public Integer[] sort(Integer array[]){
int n=array.length, i, j;
int mid = n/2;
Integer left[] = new Integer[mid];
Integer right[] = new Integer[n-mid];
for(i=0; i<mid; i++){
left[i] = array[i];
}
for(j=mid; j<n; j++){
right[j-mid] = array[j];
}
if(n<2){
return array;
} else{
sort(left);
sort(right);
array = merge(left, right, array);
left=right=null;
return array;
}
}
private Integer[] merge(Integer left[], Integer right[], Integer array[]){
int iL=0, iR=0, iA=0;
int nL = left.length, nR = right.length;
while(iL<nL && iR<nR){
if(left[iL]<=right[iR]){
array[iA] = left[iL];
iL++;
} else {
array[iA] = right[iR];
iR++;
}
iA++;
}
while(iL<nL){
array[iA] = left[iL];
iL++;
iA++;
}
while(iR<nR){
array[iA] = right[iR];
iR++;
iA++;
}
return array;
}
/******************************************************
USING GENERICS
******************************************************/
/*
array = [ Suyash Anoop Virag Sunny Abhishek Saurabh ]
[ Suyash Anoop Virag ] & [ Sunny Abhishek Saurabh ] = [ Suyash Anoop Virag Sunny Abhishek Saurabh ]
[ Suyash ] & [ Anoop Virag ] = [ Suyash Anoop Virag ]
[ Anoop ] & [ Virag ] = [ Anoop Virag ]
[ Sunny ] & [ Abhishek Saurabh ] = [ Sunny Abhishek Saurabh ]
[ Abhishek ] & [ Saurabh ] = [ Abhishek Saurabh ]
*/
@Override
public <E extends Comparable<E>> E[] genericSort(E[] array) {
int n=array.length;
int mid = n/2;
E[] left = Arrays.copyOfRange(array, 0, mid);
E[] right = Arrays.copyOfRange(array, mid, n);
if(n<2){
return array;
} else{
genericSort(left);
genericSort(right);
array = merge(left, right, array);
left=right=null;
return array;
}
}
/*
[ Anoop ] & [ Virag ] = [ Anoop Virag ]
[ Suyash ] & [ Anoop Virag ] = [ Anoop Suyash Virag ]
[ Abhishek ] & [ Saurabh ] = [ Abhishek Saurabh ]
[ Sunny ] & [ Abhishek Saurabh ] = [ Abhishek Saurabh Sunny ]
[ Anoop Suyash Virag ] & [ Abhishek Saurabh Sunny ] = [ Abhishek Anoop Saurabh Sunny Suyash Virag ]
Abhishek Anoop Saurabh Sunny Suyash Virag
*/
public <E extends Comparable<E>> E[] merge(E left[], E right[], E array[]) {
int nL = left.length, nR = right.length;
int iL = 0,iR = 0, iA=0;
while(iL<nL && iR<nR){
if( (left[iL].compareTo(right[iR])) <=0){
array[iA] = left[iL];
iL++;
} else{
array[iA] = right[iR];
iR++;
}
iA++;
}
while(iL<nL){
array[iA] = left[iL];
iL++;
iA++;
}
while(iR<nR){
array[iA] = right[iR];
iR++;
iA++;
}
return array;
}
}
//Printing logic just for testing.
/*System.out.print("[ ");
for(E eL : left){
System.out.print(eL+" ");
}
System.out.print("] ");
System.out.print(" & [ ");
for(E eR : right){
System.out.print(eR+" ");
}
System.out.print("] = ");
System.out.print("[ ");
for(E eA : array){
System.out.print(eA+" ");
}
System.out.print("] \n");
*/