-
Notifications
You must be signed in to change notification settings - Fork 1
/
Merge Sort with Temp Arrray
77 lines (70 loc) · 1.41 KB
/
Merge Sort with Temp Arrray
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
package imp;
// Sp1
public class MergeSortWA {
public static void sortWA(int[] arr, int[] temp) {
mergeSortWA(arr, temp, 0, arr.length - 1);
}
public static void mergeSortWA(int[] arr, int[] temp, int i, int j) {
int midIndex = i + j / 2;
if (j - i < 1) {
return;
} else {
System.out.println("1");
mergeSortWA(arr, temp, i, midIndex);
System.out.println("2");
mergeSortWA(arr, temp, midIndex + 1, j);
System.out.println("3");
merge(arr, temp, i, midIndex, j);
}
}
public static void merge(int[] arr, int[] temp, int p, int mid, int q) {
int i = p;
int j = mid + 1;
int k = 0;
System.out.println("4");
if(q - p == 1){
if(arr[p] > arr[q]){
int t = arr[p];
arr[p] = arr[q];
arr[q] = t;
}
}
if (q - p > 0) {
while (i <= mid && j <= q) {
if (arr[j] >= arr[i]) {
temp[k] = arr[i];
i++;
} else {
temp[k] = arr[j];
j++;
}
k++;
}
if (i <= mid && j > q) {
while (i <= mid) {
temp[k] = arr[i];
k++;
i++;
}
} else {
while (j <= q) {
temp[k] = arr[j];
k++;
j++;
}
}
for (i = p; i <= q; i++) {
arr[i] = temp[i];
}
}
}
public static void main(String[] args) {
int[] arr = { 1, 5, 3, };
int[] temp = new int[arr.length];
MergeSortWA mg = new MergeSortWA();
mg.sortWA(arr, temp);
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
}
}