import java.util.Arrays;
public class MergingSort {
public static void main(String[] args) {
int[] array = new int[]{5, 3, 9, 1, 6, 4, 10, 2, 8, 7, 15, 3, 2};
System.out.println("Before: " + Arrays.toString(array));
sort(array);
System.out.println("After: " + Arrays.toString(array));
}
public static int[] sort(int[] arr) {
int[] ans = recurse(arr, 0, arr.length - 1);
System.arraycopy(ans, 0, arr, 0, ans.length);
return ans;
}
private static int[] recurse(int[] arr, int start, int end) {
int len = end - start + 1;
if (len == 1) {
return new int[]{arr[start]};
}
int mid = (start + end) / 2;
int[] left = recurse(arr, start, mid);
int[] right = recurse(arr, mid + 1, end);
return merge(left, right);
}
private static int[] merge(int[] arr1, int[] arr2) {
int len1 = arr1.length;
int len2 = arr2.length;
int i = 0;
int j = 0;
int k = 0;
int[] result = new int[len1 + len2];
while (i < len1 && j < len2) {
if (arr1[i] <= arr2[j]) {
result[k++] = arr1[i++];
} else {
result[k++] = arr2[j++];
}
}
while (i < len1) {
result[k++] = arr1[i++];
}
while (j < len2) {
result[k++] = arr2[j++];
}
return result;
}
}