Я получаю исключение индекса за пределами границ при попытке запустить этот код.
мы используем два разных массива слева и справа для слияния ..
и используем рекурсивную сортировку слиянием, чтобы разделить массив на отдельные элементы и объединить их ...
Вот алгоритм из CLRS, который я использую:
Merge(A, p, q, r)
n1 ← q - p + 1
n2 ← r - q
create arrays L[1..n1 + 1] and R[1..n2 + 1]
for i ← 1 to n1
do L[i] ← A[p + i - 1]
for j ← 1 to n2
do R[j] ← A[q + j]
L[n1 + 1] ← ∞
L[n2 + 1] ← ∞
i ← 1
j ← 1
for k ≤ p to r
do if L[i] ≤ R[j]
then A[k] ← L[i]
i ← i + 1
else A[k] ← R[j]
j ← j + 1
MergeSort(A, p, r)
if p < r
then q ← ⌊(p + r)/2⌋
MergeSort(A, p, q)
MergeSort(A, q + 1, r)
Merge(A, p, q, r)
вот код:
import java.util.Arrays;
import java.util.Scanner;
public class MergeSort {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
System.out.println("Enter the size of array to be sorted");
int size = input.nextInt();
int[] A = new int[size];
System.out.println("Enter the elements of array");
for (int i = 0; i < A.length; i++) {
A[i] = input.nextInt();
}
System.out.println("The UNSORTED array elements are" + Arrays.toString(A));
int p = 0, r = size;
mergeSort(A, p, r);
System.out.println("The SORTED array elements are" + Arrays.toString(A));
}
public static void mergeSort(int[] A, int p, int r) {
if (p < r) {
int q = (p + r) / 2;
mergeSort(A, p, q);
mergeSort(A, q + 1, r);
merge(A, p, q, r);
}
}
public static void merge(int[] A, int p, int q, int r) {
int n1 = q - p + 1;
int n2 = r - q;
int[] L = new int[n1 + 1];
int[] R = new int[n2 + 1];
L[n1] = Integer.MAX_VALUE;
R[n2] = Integer.MAX_VALUE;
for (int i = 0; i < n1; i++) {
L[i] = A[p + i];
}
for (int j = 0; j < n2; j++) {
R[j] = A[q + j + 1];
}
int x = 0, y = 0;
for (int k = p; k < r; k++) {
if (L[x] <= R[y]) {
A[k] = L[x];
x++;
} else {
A[k] = R[y];
y++;
}
}
}
}