mergesorting 3 sub-arrays сразу

Question

Я делаю программу, которая реализует алгоритм mergesort, но вместо того, чтобы делиться каждый раз на 2 части, он каждый раз делит их по 3 части и рекурсивно решает их ретрансляцию. В случае, если я смутил вас, это в основном слияние, но вместо слияния с 2 частями вы каждый раз объединяетесь с 3, звучит довольно весело, да? Ну, это определенно не так.

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

public static void mergesort(int[] data) { 
    int elements = data.length; 
    int sizeLeft; 
    int sizeCenter; 
    int sizeRight; 

    if (elements > 2) { 

     if (elements % 3 == 0) { 
      sizeLeft = elements/3; 
      sizeCenter = elements/3; 
      sizeRight = elements/3; 
     } else if (elements % 3 == 1) { 
      sizeLeft = (elements/3) + 1; 
      sizeCenter = elements/3; 
      sizeRight = elements/3; 
     } else { //if (elements % 3 == 2) 
      sizeLeft = (elements/3) + 1; 
      sizeCenter = elements/3; 
      sizeRight = (elements/3) + 1; 
     } 

     int[] left = makeArray(data, 0, sizeLeft); 
     int[] center = makeArray(data, sizeLeft, sizeCenter); 
     int[] right = makeArray(data, sizeLeft + sizeCenter, sizeRight); 

     mergesort(left); 
     mergesort(center); 
     mergesort(right); 

     merge(data, left, center, right); 
    } 
} 

Вот метод слияния:

public static void merge(int[] data, int[] left, int[] center, int[] right) { 
    int[] temp = new int[left.length + center.length + right.length]; 
    int copiedTotal = 0; 
    int copiedLeft = 0; 
    int copiedCenter = 0; 
    int copiedRight = 0; 

    while ((copiedLeft < left.length) 
      && (copiedCenter < center.length) 
      && (copiedRight < right.length)) { 

     if ((left[copiedLeft] < center[copiedCenter]) 
       && (left[copiedLeft] < right[copiedRight])) { 

      temp[copiedTotal++] = left[(copiedLeft++)]; 
     } else if ((center[copiedCenter] < left[copiedLeft]) 
       && (center[copiedCenter] < right[copiedRight])) { 
      temp[copiedTotal++] = center[copiedCenter++]; 
     } else { 
      temp[copiedTotal++] = right[copiedRight++]; 
     } 
    } 

    while ((copiedLeft < left.length) && (copiedCenter < center.length)) { 
     if (left[copiedLeft] < center[copiedCenter]) { 
      temp[copiedTotal++] = left[copiedLeft++]; 
     } else{ 
      temp[copiedTotal++] = center[copiedCenter++]; 
     } 
    } 

    while ((copiedLeft < left.length) && (copiedRight < right.length)) { 
     if (left[copiedLeft] < right[copiedRight]) { 
      temp[copiedTotal++] = left[copiedLeft++]; 
     } else{ 
      temp[copiedTotal++] = right[copiedRight++]; 
     } 
    } 

    while ((copiedCenter < center.length) && (copiedRight < right.length)) { 
     if (center[copiedCenter] < right[copiedRight]) { 
      temp[copiedTotal++] = center[copiedCenter++]; 
     } else{ 
      temp[copiedTotal++] = right[copiedRight++]; 
     } 
    } 

    while (copiedLeft < left.length) { 
     temp[copiedTotal++] = left[copiedLeft++]; 
    } 

    while (copiedCenter < center.length) { 
     temp[copiedTotal++] = center[copiedCenter++]; 
    } 

    while (copiedRight < right.length) { 
     temp[copiedTotal++] = right[copiedRight++]; 
    } 
    System.arraycopy(temp, 0, data, 0, left.length + center.length + right.length); 
//  for (int i = 0; i < data.length; i++) { 
//   if ((copiedRight >= right.length) && (copiedCenter >= center.length)) { 
//    data[i] = left[copiedLeft]; // take from left 
//    copiedLeft++; 
//   } else if ((copiedRight >= right.length) && (copiedLeft >= left.length)) { 
//    data[i] = center[copiedCenter]; // take from left 
//    copiedCenter++; 
//   } else if ((copiedCenter >= center.length) && (copiedLeft >= left.length)) { 
//    data[i] = right[copiedRight]; // take from left 
//    copiedRight++; 
//   } else if ((copiedLeft < left.length 
//     && left[copiedLeft] <= right[copiedRight]) 
//     && left[copiedLeft] <= center[copiedCenter]) { 
// 
//    data[i] = left[copiedLeft]; // take from left 
//    copiedLeft++; 
// 
//   } else if ((copiedRight >= right.length) && (copiedLeft >= left.length) 
//     || (copiedCenter < center.length 
//     && center[copiedCenter] <= right[copiedRight]) 
//     && center[copiedCenter] <= left[copiedLeft]) { 
// 
//    data[i] = center[copiedCenter]; // take from center 
//    copiedCenter++; 
//   } else { 
//    data[i] = right[copiedRight]; 
//    copiedRight++;// take from center 
//   } 
// 
//  } 
    } 
} 

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

Проблема заключается в том, это не работает вообще, если у меня есть:

Вход: 6 5 4 3 2 1

Тогда я буду иметь:

Выход: [ 2, 1, 4, 3, 6, 5]

Я честно так старался за это и в течение двух дней подряд, я обнаружил, что только два человека слышали об этом виде слияния и после нескольких часов в Google, я только нашел здесь аналогичный вопрос (что было слишком сложно понять) и другой поток в вики-ответах, на которые никогда не отвечали.

Любая помощь будет принята с благодарностью, конечно, я не прошу прямого решения, потому что я пытаюсь учиться, но советы и подсказки, а также то, что я сделал неправильно, очень помогло бы мне.

Заранее спасибо.

Answer 1

Кажется, проблема в том, что когда у вас есть массив из 2 элементов, вы ничего не делаете с ним. Вы должны отсортировать его. Если вы примете свой пример: [6,5,4,3,2,1], на втором этапе рекурсии у вас есть [2,1]; [4,3] и [6,5], и вы объедините их так. Если вы сначала отсортируете их, вы получите правильный заказ. Для того, чтобы отсортировать их в функции слияния следует добавить:

if ((elements==2)&&(data[1]<data[0])){ 
int aux = data[1]; 
data[1] = data[0]; 
data[0] = aux; 

}

Надеется, что это помогает.

UPDATE

Если вы хотите иметь чистые сортировки слияния вы можете попробовать (как я объяснил в комментарии), чтобы добавить следующий фрагмент кода:

if (elements==2){ 
int[] center = []; 
int[] left = makeArray(data,0,1); 
int[] right =makeArray(data,1,1); 

mergesort(left); //you can call these methods or not, on a empty or 1 element array they dont have an effect 
mergesort(center); 
mergesort(right); 

merge(data, left, center, right); //it should work well when center is an empty array 

}

UPDATE 2 Вы можете реорганизовать код, показанный мной, чтобы он выглядел красиво. Основная идея заключается в том, что вы можете иметь пустой массив в Java, и ваша функция слияния работает с ним должным образом. Надеюсь, я немного уточнил.