Блог

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

Пример вывода:

 [23, 94, 69, 32, 99, 20, 17, 88, 22, 88]
  

Сортировка слиянием заняла 7,134364 миллисекунды

оригинал: [17, 20, 22, 23, 32, 69, 88, 88, 94, 99] //Arrays.sort

working1: [17, 20, 22, 23, 32, 68, 88, 94, 99, 88] //MergeSort

Ошибка

 import java.util.*;

public class MergeSort {
public static void mergeSortExplicit(int[] arr, int n){
    int size;  
    int left; 

    for (size = 1; size <= n-1; size = 2*size) {  
        for (left = 0; left < n-1; left  = 2*size) { 
            int mid = left   size - 1; 

            int right = Math.min(left   2*size - 1, n-1);

            merge(arr, left, mid, right);
        } 
    } 
 }
private static void merge(int[] array, int start, int mid, int end) {
    int leftIndex = start;
    int rightIndex = mid   1;
    int[] temp = new int[end - start   1];
    int tempIndex = 0;

    while (leftIndex <= mid amp;amp; rightIndex <= end) {

        temp[tempIndex  ] = (array[leftIndex] < array[rightIndex]) ? array[leftIndex  ] : array[rightIndex  ];

    }

    if (leftIndex <= mid) {
        System.arraycopy(array, leftIndex, temp, tempIndex, mid - leftIndex   1);
    }

    if (rightIndex <= end) {
        System.arraycopy(array, rightIndex, temp, tempIndex, end - rightIndex   1);
    }

    System.arraycopy(temp, 0, array, start, end - start   1);

}

public static final void main(String[] args) {
    Random random = new Random();
    int[] original = new int[10];
    for (int i = 0; i < original.length; i  ) {
        original[i] = random.nextInt(original.length * 10);
    }
    int[] working1 = new int[original.length];
    System.arraycopy(original, 0, working1, 0, original.length);

    long startTime = 0, endTime = 0;

    startTime = System.nanoTime();
    Arrays.sort(original);
    endTime = System.nanoTime();
    System.out.println("Arrays.sort() took "   ((endTime - startTime) / 1E6)   " milliseconds");

    startTime = System.nanoTime();
    //mergeSort(working1, 0, working1.length - 1);
     System.out.println(Arrays.toString(working1));
    mergeSortExplicit(working1, working1.length - 1);
    endTime = System.nanoTime();
    System.out.println("MergeSort took "   ((endTime - startTime) / 1E6)   " milliseconds");

    if (!Arrays.equals(original, working1)) {
        System.out.println("original: "   Arrays.toString(original));
        System.out.println("Working1: "   Arrays.toString(working1));
        System.out.println("There is an error");
    } else {
        System.out.println("Sorts Work!");
    }
}

}
  

Просто просматривая, я вижу, что вы вызываете следующую функцию в main :

 mergeSortExplicit(working1, working1.length - 1);
  

это означает, что вы уже вызываете функцию с размером на 1 меньше, чем фактический размер, а затем снова внутри этой вызываемой функции в следующем цикле :

 for (size = 1; size <= n-1; size = 2*size)
  

вы снова рассматриваете на 1 меньше того, что вы передали.

Пожалуйста, удалите любое из вышеуказанных уменьшений, тогда оно должно работать нормально.