Java реализация MergeSort; не могу найти ошибку

Question

Хорошо, это один из тех отчаянных вопросов. Я пытаюсь реализовать Bottom-Up MS для сортировки и целочисленного массива. Но ради бога, я не могу найти ошибку ...

import java.util.Scanner;

public class A2 {

    public static boolean less(Integer v, Integer w) {
        return v.compareTo(w) < 0;
    }

    public static void sort(int[] a) {
        int N = a.length;
        int[] aux = new int[N];
        for (int sz = 1; sz < N; sz = sz + sz)
            for (int lo = 0; lo < N - sz; lo += sz + sz)
                merge(a, aux, lo, lo + sz - 1, Math.min(lo + sz + sz - 1, N - 1));
    }

    public static void merge(int[] a, int aux[], int lo, int mid, int hi) {
        int i = lo;
        int j = mid + 1;

        for (int k = lo; k <= hi; k++)
            aux[k] = a[k];

        for (int k = lo; k <= hi; k++) 
            if (i > mid)
                a[k] = aux[j++];
            else if (j > hi)
                a[k] = aux[i++];
            else if (less(aux[j], aux[i]))
                a[k] = a[j++];
            else
                a[k] = a[i++];

    }

    public static void main(String[] args) {
        int next = 0;
        Scanner scanner = new Scanner(System.in);
        int size = Integer.parseInt(scanner.nextLine());
        int[] v = new int[size];
        String s = scanner.nextLine();
        scanner.close();
        String[] sa = s.split("[\\s]+");
        while (next < size) {
            v[next] = Integer.parseInt(sa[next]);
            next ++;
        }
        for (Integer i : v)
            System.out.print(i + " ");
        System.out.println();
        System.out.println("----------------------------------");
        sort(v);
        for (int i = 0; i < size; i++)
            System.out.print(v[i] + " ");
        System.out.println();
    }
}

В функции main я печатаю элементы массива, просто чтобы убедиться, что проблема в сортировка. Первое число - это просто размер массива. Ошибка либо в sort(), либо в merge(). Вот несколько примеров выходных данных:

9
10 45 20 5 -6 80 99 -4 0
10 45 20 5 -6 80 99 -4 0 
----------------------------------
-6 -4 -4 -6 -4 -4 -6 0 99 

6
6 7 3 2 4 1
6 7 3 2 4 1 
----------------------------------
1 1 1 4 6 7 

5
6 5 2 3 4
6 5 2 3 4 
----------------------------------
2 3 4 5 6 

Этот последний выглядит просто отлично.

Пожалуйста, помогите мне, я ходил вокруг и не могу найти ошибку.

Answer 1

Проблема в методе merge(): в последних 2 случаях в l oop вы копируете значения из a вместо aux. Это не проблема при копировании a[j++], но при копировании a[i++] значение может быть уже перезаписано.

Учитывая, что значения в правом срезе записываются только после того, как они уже скопированы, вам нужно только сохранить левый фрагмент.

Вот модифицированная версия с этим упрощением:

    public static void merge(int[] a, int aux[], int lo, int mid, int hi) {
        int i = lo;
        int j = mid + 1;

        for (int k = lo; k <= mid; k++)  // save a[lo..mid] to aux
            aux[k] = a[k];

        for (int k = lo; k <= hi; k++) {
            if (i > mid)
                a[k] = a[j++];
            else if (j > hi)
                a[k] = aux[i++];
            else if (less(a[j], aux[i]))
                a[k] = a[j++];
            else
                a[k] = aux[i++];
        }
    }

Обратите внимание, что было бы менее склонным к ошибкам считать mid началом правого среза и hi - индекс после конца среза. sort() l oop будет проще, без хитрых настроек +/- 1. Кстати, внутренний тест l oop в вашей версии отключен одним, хотя и без последствий, кроме неэффективности. Это должно быть:

for (int lo = 0; lo < N - sz - 1; lo += sz + sz)

Вот еще одна упрощенная реализация с включенными / исключенными слайсами и комбинированным тестом:

    public static void sort(int[] a) {
        int N = a.length;
        int[] aux = new int[N];
        for (int sz = 1; sz < N; sz = sz + sz)
            for (int lo = 0; lo < N - sz; lo += sz + sz)
                merge(a, aux, lo, lo + sz, Math.min(lo + sz + sz, N));
    }

    public static void merge(int[] a, int aux[], int lo, int mid, int hi) {
        for (int i = lo; i < mid; i++) { // save a[lo..mid[ to aux
            aux[i] = a[i];
        }
        for (int i = lo, j = mid, k = lo; i < mid; k++) {
            if (j < hi && less(a[j], aux[i]))
                a[k] = a[j++];
            else
                a[k] = aux[i++];
        }
    }

Эта версия очень проста, но все же не очень эффективна для больших массивов, потому что каждый проход проходит через весь массив, побеждая схему кэширования процессора. Было бы более эффективно постепенно выполнять слияние снизу вверх, используя стек отсортированных подмассивов увеличивающихся размеров.

Answer 2

С этим изменением, это работает в моей системе.

            else if(less(aux[j], aux[i]))
                a[k] = aux[j++];             // fix  (aux)
            else
                a[k] = aux[i++];             // fix  (aux)

Если сортировка слиянием избегала шага копирования, изменяя направление слияния с каждым проходом, если в конец прохода слияния, его нужно скопировать. В третьем разделе этого ответа есть пример этого.

---

Использование less (...) периодически удваивает время выполнения в моей системе, когда я тестировал с использованием больших массивов (например, 8 миллионов ints) со случайными значениями. Изменение if (less (aux [j], aux [i])) на if (aux [j]

---

Пример код для несколько более эффективной сортировки слиянием, которая позволяет избежать создания копий, если нет нечетного числа проходов. Этого можно избежать, сначала посчитав количество проходов, а если число проходов нечетное, поменяйте местами. Это можно распространить на более крупные подгруппы с помощью сортировки вставок по группам из 32 или 64 элементов на начальном проходе.

    public static void sort(int[] a) {
        int n = a.length;
        if(n < 2)
            return;
        int[] dst = new int[n];
        int[] src = a;
        int[] tmp;
        for(int sz = 1; sz < n; sz = sz+sz){
            int lo;
            int md;
            int hi = 0;
            while(hi < n){
                lo = hi;
                md = lo+sz;
                if(md >= n){            // if single run remaining, copy it
                    System.arraycopy(src, lo, dst, lo, n-lo);
                    break;
                }
                hi = md+sz;
                if(hi > n)
                    hi = n;
                merge(src, dst, lo, md, hi);
            }
            tmp = src;                  // swap references
            src = dst;                  //  to change direction of merge
            dst = tmp;
        }
        if(src != a)                    // copy back to a if needed
            System.arraycopy(src, 0, a, 0, n);
    }

    public static void merge(int[] src, int[] dst, int lo, int md, int hi) {
        int i = lo;
        int j = md;
        int k = lo;
        while(true){
            if(src[j]< src[i]){
                dst[k++] = src[j++];
                if(j < hi)
                    continue;
                System.arraycopy(src, i, dst, k, md-i);
                return;
            } else {
                dst[k++] = src[i++];
                if(i < md)
                    continue;
                System.arraycopy(src, j, dst, k, hi-j);
                return;
            }
        }
    }

Answer 3

Вы можете попробовать с этим кодом:

import java.util.Arrays;

public class MergeSort
{
   public static void merge(double[] a, 
                            int iLeft, int iMiddle, int iRight, 
                            double[] tmp)
   {
      int i, j, k;

      i = iLeft;
      j = iMiddle;
      k = iLeft;

      while ( i < iMiddle || j < iRight )
      {
         if ( i < iMiddle && j < iRight )
         {  // Both array have elements
            if ( a[i] < a[j] )
               tmp[k++] = a[i++];
            else
               tmp[k++] = a[j++];
         }
         else if ( i == iMiddle )
            tmp[k++] = a[j++];     // a is empty
         else if ( j == iRight )
            tmp[k++] = a[i++];     // b is empty
      }

      /* =================================
         Copy tmp[] back to a[]
         ================================= */
      for ( i = iLeft; i < iRight; i++ )
         a[i] = tmp[i];
   }

   public static void sort(double[] a, double[] tmp)
   {
      int width;

      for ( width = 1; width < a.length; width = 2*width )
      {
         // Combine sections of array a of width "width"
         int i;

         for ( i = 0; i < a.length; i = i + 2*width )
         {
            int left, middle, right;

        left = i;
        middle = i + width;
        right  = i + 2*width;

            merge( a, left, middle, right, tmp );

         }

         System.out.println("After 1 iter: " + Arrays.toString(a) );
      }
   }
}