возникли проблемы с алгоритмом слияния

Question

В настоящее время я пытаюсь переписать алгоритм сортировки слиянием с уровня псевдокода на работающую реализацию в Java. Это мой код

public int[] merge(int a[], int b[]) {
        int c[] = new int[a.length + b.length];
        int i = 0, j = 0;
        for (int k = 0; k < c.length; k++) {
            if (a[i] <= b[j]) {
                c[k] = a[i++];
            } else {
                c[k] = b[j++];
            }
        }
        return c;
    }

Насколько мне известно, интерпретация псевдокода является правильной, но она продолжает возвращать исключение ArrayOutofBound. Где я все понял неправильно

Answer 1

Это, очевидно, даст исключение вне границы, поскольку вы не отслеживаете длину массивов a и b. Поскольку k = a + b, a и b всегда будут меньше k. Отсюда и исключение.

И когда вы применяете эту проверку, не забудьте скопировать оставшиеся элементы, будь то a[] или b[], чтобы скопировать их в c[]. Смотрите это -

for(;i<a.length;i++)
    c[k++] = a[i++];

for(;j<b.length;b++)
    c[k++] = b[j++];

Answer 2

Алгоритм слияния в том виде, в котором вы собираетесь его реализовать, немного сложнее, ниже вы найдете правильную реализацию:

public int[] merge(int a[], int b[]) {

    int i = 0, j = 0, k = 0;
    int m = a.length, n = b.length;
    int[] c = new int[m + n];

    // Merge to the end of one of the source arrays
    while (i < m && j < n) {
        if (a[i] <= b[j]) {
            c[k] = a[i];
            i++;
        } else {
            c[k] = b[j];
            j++;
        }
        k++;
    }

    // Determine which source array has elements remaining and
    // append those to the result array
    if (i < m) {
        for (int p = i; p < m; p++) {
            c[k] = a[p];
            k++;
        }
    } else {
        for (int p = j; p < n; p++) {
            c[k] = b[p];
            k++;
        }
    }

    return c;

}