Блог

 // merge operation for merge sort
private static void merge(int[] a, int left, int middle, int right) {
    int[] temp = new int[right - left   1];        
    int leftCrawler = left, rightCrawler = middle;
    int currentIndex = 0;

    while (leftCrawler < middle amp;amp; rightCrawler <= right) {
        if (a[leftCrawler] < a[rightCrawler])
            temp[currentIndex  ] = a[leftCrawler  ];
        else
            temp[currentIndex  ] = a[rightCrawler  ];
    }

    while (leftCrawler < middle)
        temp[currentIndex  ] = a[leftCrawler  ];

    while (rightCrawler <= right)
        temp[currentIndex  ] = a[rightCrawler  ];

    // copy temp into a
    for (int i = 0; i < temp.length; i  )
        a[i] = temp[i];
}

private static void mergeSort(int[] a, int left, int right) {
    if (right > left) {
        int middle = left   (right - left) / 2;
        mergeSort(a, left, middle);
        mergeSort(a, middle   1, right);
        merge(a, left, middle, right);
    }
}

public static void mergeSort(int[] a) {
    int left = 0, right = a.length - 1;
    mergeSort(a, left, right);
}
  

Итак, я подумал, что проблема может быть в моей операции слияния, однако я протестировал ее на следующем массиве int[] a = {2, 5, 7, 15, 8, 9, 10} с left = 0 , middle = 4 и right = a.length - 1 , и операция слияния успешно выполняет то, что ей нужно.

Я сравнил свою реализацию сортировки слиянием с теми, что есть на разных веб-сайтах, и я не могу заметить разницы. Моя сортировка слиянием не приведет к успешной сортировке массива. Что я делаю не так?

В вашем коде 3 ошибки:

• цикл слияния не включает элемент at, a[middle] потому что вы используете leftCrawler < middle вместо:

     while (leftCrawler <= middle amp;amp; rightCrawler <= right)
    

• второй цикл while (leftCrawler < middle) также должен быть изменен на:

     while (leftCrawler <= middle)
    

• цикл для копирования из temp обратно в a использует неверный индекс в a . Это должно быть:

         // copy temp into a
        for (int i = 0; i < temp.length; i  )
            a[left   i] = temp[i];
    

Обратите внимание, что первая ошибка коренится в используемом здесь вредоносном соглашении, где right и middle включены в срезы вместо исключенных. Исключение правильных границ позволяет упростить код без каких-либо подверженных ошибкам 1 / -1 корректировок.

Вот измененная версия:

 // merge operation for merge sort
private static void merge(int[] a, int left, int middle, int right) {
    int[] temp = new int[right - left];        
    int leftCrawler = left, rightCrawler = middle;
    int currentIndex = 0;

    while (leftCrawler < middle amp;amp; rightCrawler < right) {
        if (a[leftCrawler] < a[rightCrawler])
            temp[currentIndex  ] = a[leftCrawler  ];
        else
            temp[currentIndex  ] = a[rightCrawler  ];
    }

    while (leftCrawler < middle)
        temp[currentIndex  ] = a[leftCrawler  ];

    while (rightCrawler < right)
        temp[currentIndex  ] = a[rightCrawler  ];

    // copy temp into a
    for (int i = 0; i < temp.length; i  )
        a[left   i] = temp[i];
}

private static void mergeSort(int[] a, int left, int right) {
    if (right - left >= 2) {
        int middle = left   (right - left) / 2;
        mergeSort(a, left, middle);
        mergeSort(a, middle, right);
        merge(a, left, middle, right);
    }
}

public static void mergeSort(int[] a) {
    mergeSort(a, 0, a.length);
}
  

Проблема может быть в вашей копии:

     // copy temp into a
    for(int i = 0; i < temp.length; i  )
        a[i] = temp[i];
  

Что вы, вероятно, хотите (обратите внимание на left i ):

     // copy temp into a
    for(int i = 0; i < temp.length; i  )
        a[left   i] = temp[i];
  

(Ваш тест не обнаружил проблему, так как left было 0.)