Mergesort неправильно сортирует

Question

Я попытался реализовать сортировку слиянием в Java, используя код ниже. Предполагается, что метод mergeSort() является рекурсивным методом, который многократно разделяет массив на более мелкие секции, а метод merge() берет 2 секции массива, которые уже были отсортированы, и объединяет их в одну отсортированную секцию.

Вот код:

class MergeSort{
    public static void mergeSort(int[] array){
        mergeSort(array, 0, array.length-1);
    }
    public static void mergeSort(int[] array, int start, int end){
        int mid = (start + end)/2;
        if (end > start) {
            mergeSort(array, start, mid);
            mergeSort(array, mid + 1, end);
            merge(array, start, end, mid + 1);
        }
    }
    public static void merge(int[] array, int start, int end, int  mid){
        int length = end - start + 1,length1 = mid- start, length2 = end - mid + 1, index1 = start, index2 = mid, sortedindex = 0;
        boolean cont = true;
        int[] sortedArray = new int[length];
        while (cont){
            if (array[index1] > array[index2]){
                sortedArray[sortedindex] = array[index2];
                index2++;
            } else{
                sortedArray[sortedindex] = array[index1];
                index1++;
            }
            sortedindex++;
            //reached the end of one array, dump the rest of the remaining array in the sorted array
            if (index1 >= length1){
                for (index2 = index2; index2 < length2; index2++){
                    sortedArray[sortedindex] = array[index2];
                    sortedindex++;
                }
                cont = false;
            } else if (index2 >= length2){
                for (index1 =index1; index1 < length1; index1++){
                    sortedArray[sortedindex] = array[index1];
                    sortedindex++;
                }
                cont = false;
            }
        }
        //copy the sorted array into the main array
        for (int i = 0; i <= length - 1; i++){
            array[start+i] = sortedArray[i];
        }
    }
}

public class Main {

    public static void main(String[] args) {
    // write your code here
        Scanner scanner = new Scanner(System.in);
        scanner.useDelimiter("\n");
        Random random = new Random();
        int length = scanner.nextInt();
        int[] array = new int[length];
        for (int i = 0; i < length;i++){
            array[i] = random.nextInt(5000);
            //System.out.println(array[i]);
        }
        MergeSort.mergeSort(array);
        for (int i: array){
            System.out.println(i);
        }
    }
}

Затем основной класс генерирует массив определенной пользователем длины, заполняет его случайными целыми числами и передает его в mergeSort().

К сожалению, программа выводит массив, в котором первые несколько элементов отсортированы правильно, а остальные - нули. например, учитывая произвольно сгенерированный массив {3291, 2879, 3078, 3609, 3534, 3922, 2793, 1098, 472, 1800}, программа выводит {472, 2879, 3291, 0, 0, 0, 0, 0, 0, 0}, причем количество правильно отсортированных элементов в выходных данных отличается от запуска к запуску.

Кажется, я не могу понять, что не так с мой код Любая помощь будет принята с благодарностью:)

Answer 1

, в то время как l oop должно закрыться раньше.

public static void merge1(int[] array, int start, int end, int mid) {
    int length = end - start + 1;
    int[] sortedArray = new int[length];
    int index1 = start;
    int index2 = mid + 1;
    int sortedindex = 0;
    while (index1 <= mid && index2 <= end) {
        if (array[index1] < array[index2]) {
            sortedArray[sortedindex++] = array[index1++];
        } else {
            sortedArray[sortedindex++] = array[index2++];
        }
    }
        // reached the end of one array, dump the rest of the remaining array in the
        // sorted array
        while (index1 <= mid) {
            sortedArray[sortedindex++] = array[index1++];
        }

        while (index2 <= end) {
            sortedArray[sortedindex++] = array[index2++];
        }

    // copy the sorted array into the main array
    for (int i = 0; i <= length - 1; i++) {
    array[start + i] = sortedArray[i];
    }
}