- 01
- 02
- 03
- 04
- 05
- 06
- 07
- 08
- 09
- 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
public class Sorting {
private static void swapElements(int[] arr, int index1, int index2) {
int temp = arr[index1];
arr[index1] = arr[index2];
arr[index2] = temp;
}
public static void mergeSort(int[] arr) {
if (arr.length == 1) {
return;
}
final int temp = (arr.length % 2 == 0) ? arr.length / 2 : (arr.length + 1) / 2;
int[] left = new int[temp];
int[] right = new int[arr.length / 2];
System.arraycopy(arr, 0, left, 0, temp);
System.arraycopy(arr, temp, right, 0, arr.length / 2);
Sorting.mergeSort(left);
Sorting.mergeSort(right);
Sorting.mergeSortHelper(arr, left, right);
}
private static void mergeSortHelper(int[] arr, int[] left, int[] right) {
int L = 0, R = 0;
boolean Ltop = false, Rtop = false;
for (int i = 0; i < arr.length; i++) {
if (L < left.length - 1 && R < right.length - 1) {
if (left[L] <= right[R]) {
arr[i] = left[L];
L++;
} else {
arr[i] = right[R];
R++;
}
} else if ((L == left.length - 1) ^ (R == right.length - 1)) {
if (L == left.length - 1) {
if ((left[L] <= right[R]) && !Ltop) {
arr[i] = left[L];
Ltop = true;
} else {
arr[i] = right[R];
R++;
}
} else {
if ((right[R] <= left[L]) && !Rtop) {
arr[i] = right[R];
Rtop = true;
} else {
arr[i] = left[L];
L++;
}
}
} else {
if (i < arr.length - 1) {
arr[i] = (left[L] < right[R]) ? left[L] : right[R];
} else {
arr[i] = (left[L] > right[R]) ? left[L] : right[R];
}
}
}
}