1public static void mergeSort(int[] a, int n) {
2 if (n < 2) {
3 return;
4 }
5 int mid = n / 2;
6 int[] l = new int[mid];
7 int[] r = new int[n - mid];
8
9 for (int i = 0; i < mid; i++) {
10 l[i] = a[i];
11 }
12 for (int i = mid; i < n; i++) {
13 r[i - mid] = a[i];
14 }
15 mergeSort(l, mid);
16 mergeSort(r, n - mid);
17
18 merge(a, l, r, mid, n - mid);
19}
20
1public static void merge(
2 int[] a, int[] l, int[] r, int left, int right) {
3
4 int i = 0, j = 0, k = 0;
5 while (i < left && j < right) {
6 if (l[i] <= r[j]) {
7 a[k++] = l[i++];
8 }
9 else {
10 a[k++] = r[j++];
11 }
12 }
13 while (i < left) {
14 a[k++] = l[i++];
15 }
16 while (j < right) {
17 a[k++] = r[j++];
18 }
19}
20