Алгоритм слияния Java

Question

public class mergesort {
public static int[] mergesort (int[] input) {
    int length = input.length;
    if (length <= 1) {
        return input;
    }
    int median = length/2;
    int[] left = new int[median];
    int[] right = new int[length-median];
    for (int x = 0; x< median; x++) {
        left[x] = input[x];
    }
    for (int y = median; y < length; y++) {
        right[y-median] = input[y];
    }
    mergesort(left);
    mergesort(right);
    merge(left, right, input);
    return input;
}
public static int[] merge (int[] left, int[] right, int[] input) {
    int a = 0;
    int b = 0;
    int c = 0;
    int leftlength = left.length;
    int rightlength = right.length;
    while (a<leftlength && b<rightlength) {
        if (left[a] < right[b]) {
            input[c] = left[a];
            a++;
        } else {
            input[c] = right[b];
            b++;
        }
        c++;
    }
    return input;
}

public static void main(String[] args) {
    int[] inputArr = {45,23,11,89,77,98,4,28,65,43};
    mergesort mms = new mergesort();
    inputArr = mms.mergesort(inputArr);
    for(int i = 0; i < inputArr.length; i ++){
        System.out.print(inputArr[i]);
        System.out.print(" ");
    }
}

Это выше моя попытка алгоритма сортировки слиянием. Последний блок кода с main(String[] args) - это тестовый прогон, чтобы проверить, работает ли мой алгоритм.

Код все еще распечатывает массив (раньше он просто сбрасывал ошибку). Однако пока алгоритм должен печатать

4, 11, 23, 28, 43, 45, 65, 77, 89,and 98, 

код распечатывается:

4 4 11 23 23 28 65 43 65 43, 

что явно не является намеченным результатом.

Как я могу исправить свой код?

Это мой первый пост здесь, поэтому, пожалуйста, дайте мне знать, если мне не разрешено публиковать подобные материалы и т. Д.

Редактировать: Это (на удивление) отредактированная версия исходного кода. Раньше код сбрасывал ошибку, но теперь по крайней мере он что-то печатает. Манипулирование небольшими частями кода (например, изменение медианы на медиану + 1 и т. Д.) Не сработало, и я не думал, что было бы очень важно опубликовать множество результатов испытаний и неудач, которые могут считаться незначительным для некоторых.

И да, я, честно говоря, не знал, куда идти отсюда. Я попросил моего друга просмотреть код, и он использовал отладчик для проверки кода, но значимых открытий не было, поэтому этот пост.

Answer 1

Шаг слияния написан таким образом, что он не может использовать весь свой ввод. Цикл завершается, как только один из массивов для объединения полностью используется, что нежелательно. Это можно исправить, используя любой массив на следующем шаге следующим образом.

public static int[] merge(int[] left, int[] right, int[] input)
{
    int a = 0;
    int b = 0;
    int c = 0;
    int leftlength = left.length;
    int rightlength = right.length;
    while (a < leftlength && b < rightlength)
    {
        if (left[a] < right[b])
        {
            input[c] = left[a];
            a++;
        }
        else
        {
            input[c] = right[b];
            b++;
        }
        c++;
    }
    while (a < leftlength)  // subsequent consumption of left
    {
        input[c] = left[a];
        a++;
        c++;
    }
    while (b < rightlength) // subsequent consumption of right
    {
        input[c] = right[b];
        b++;
        c++;
    }
    return input;
}

Обратите внимание, что петли также могут быть помещены в одну петлю; было бы необходимо проверить a и b против leftlength и rightlength соответственно, чтобы решить, следует ли проводить сравнение или нужно добавить один элемент. В более компактной форме C-ish это может выглядеть следующим образом.

public static int[] merge(int[] left, int[] right, int[] input)
{
    int a = 0;
    int b = 0;
    int c = 0;
    int cval = 0;
    int leftlength = left.length;
    int rightlength = right.length;
    while (a < leftlength || b < rightlength)   // <-- note the changed condition
    {
        if (a == leftlength)
        {
            cval = right[b++];
        }
        else if (b == rightlength)
        {
            cval = left[a++];
        }
        else
        {
            cval = left[a] < right[b] ? left[a++] : right[b++];
        }
        input[c++] = cval;
    }
    return input;
}