Проблема с алгоритмом сортировки слиянием A Java

Question

У меня проблемы с этим алгоритмом сортировки слиянием. У меня есть всего 3 метода, чтобы сделать сортировку слиянием, плюс основной метод, вызывающий ее. Это не выводит отсортированный массив, и я не уверен, где я ошибся. Мне все кажется правильным, когда я смотрю на это, я не уверен, что ошибка в рекурсивных частях метода или в одном из классов. Любая помощь будет оценена, спасибо! Вот мой код:

/**
 * To do: Implement merge sort.
 * @param array the array to sort
 * @return the sorted array
 */
public static int[] mergeSort(int[] array) {
    // call mergeSort(int [], int, int) to initiate sorting
    //throw new UnsupportedOperationException()
    return mergeSort(array, 0, array.length-1);
}

/**
 * To do: Implement overloaded merge sort method.
 * @param array the array to sort
 * @param begin the starting index of the array to be sorted
 * @param end the last index of the array to be sorted
 */
private static int[] mergeSort(int[] array, int begin, int end) {
    // you need to write the merge sort algorithm here
    // use this method mergeSort(int [], int, int) and merge(int [], int[])
    // to complete it
    //throw new UnsupportedOperationException();


    if(begin < end) {
        int [] left = new int[array.length/2];
        int [] right = new int[array.length - left.length];

        //copies first half of array into left
        for(int i = 0; i < left.length; i++) {
            left[i] = array[i];
        }
        //copies second half into right array
        for(int j = 0; j < right.length; j++) {
            right[j] = array[left.length + j];
        }

        mergeSort(left);
        mergeSort(right);
        return merge(left, right);
    }
    return array;
}


/**
 * To do: Merge two sorted arrays into one and return it
 * @param left the first array
 * @param right the second array
 * @return the sorted merged array
 */
private static int[] merge(int[] left, int[] right) {
    // merge two sorted array such way that it remains sorted
    //throw new UnsupportedOperationException();
    int [] sorted = new int[left.length + right.length];

    int leftIndex = 0;
    int rightIndex = 0;

    for(int j = 0; j < sorted.length; j++ ) {
        if( leftIndex <= left.length-1 && rightIndex <= right.length-1) {

            if(left[leftIndex] < right[rightIndex]) {
                sorted[j] = left[leftIndex];
                leftIndex++;
            }
            else {
                sorted[j] = right[rightIndex];
                rightIndex++;
            }
        }
        else if( leftIndex < left.length) {
            sorted[j] = left[leftIndex];
            leftIndex++;
        }
        else if(rightIndex< right.length) {
            sorted[j] = right[rightIndex];
            rightIndex++;
        }
    }

    return sorted;
}

Answer 1

Ваша mergeSort функция не на месте, то есть она возвращает новый массив вместо изменения порядка элементов в том же массиве. Следовательно, эти 2 строки:

            mergeSort(left);
            mergeSort(right);

не будут иметь абсолютно никаких эффектов.

Измените его на:

            left = mergeSort(left);
            right = mergeSort(right);

Еще один комментарий: Даже если сортировка слиянием O(NlogN), вы используете много копирующих массивов, что создает много накладных расходов. Старайтесь использовать как можно больше операций на месте, избегая создания дополнительного массива. Чаще всего сортировка слиянием использует не более 2-х массивов одновременно.

Answer 2

Привет, я думаю, что мы в одном классе. Вы должны использовать значения «begin» и «end» для создания подмассива из исходного параметра массива. После этого вы можете разделить его на «правый» и «левый», аналогично тому, что вы уже сделали.

Что касается метода merge (), я бы порекомендовал посмотреть код в учебнике. Единственное различие между кодом в книге и нашим назначением состоит в том, что мы должны создать массив результатов внутри метода:

int[] array = new int[left.length-right.length];

, а затем вернуть его, когда это будет сделано. Надеюсь, что это помогло.