有一種工作合併排序，但不完全，有人可以告訴我我做錯了什麼？

Question

首先，我想從我的方法背後的推理開始。我的想法是，我要麼餵食偶數或奇數的數組。這個數組將在二維數組中被分解爲原始數組的長度，每個索引都有一個大小爲1的數組。然後，我將繼續合併索引。這適用於長度爲2,4,8,16的長度。現在，我不得不編輯我的方法，因爲3,5,6,7不工作。現在，我的問題是，即使他們工作，並非所有案件的工作。例如，25的長度不能正確返回。下面是我的代碼：

/** 
* A method to perform a merge sort 
* @param array The array being fed in 
*/ 
public static int[] mergeSort(int[] array) 
{ 
    if (array.length == 1) 
    { 
    return array; 
    } 

    int size = array.length; 
    int[][] miniArrayList = new int[size][1]; 

    for (int index = 0; index < array.length; index++) 
    { 
    miniArrayList[index][0] = array[index]; 
    } 

    while (miniArrayList.length > 1) 
    { 
    if (miniArrayList.length % 2 == 0) 
    { 
     miniArrayList = mergeEven(miniArrayList); 
    } 
    else 
    { 
     miniArrayList[0] = mergeOdd(miniArrayList); 
    } 
    } 
    return miniArrayList[0]; 
} 

我對上述方法的想法是，我喂的，它打破它一個數組，然後一點一點地融合了陣，直到我有大小爲1的數組排序。上述方法調用以下方法：

private static int[][] mergeEven(int[][] array) 
{ 
    int[][] tempSortList = new int[array.length/2][]; 
    int tempIndex = 0; 
    for (int index = 0; index < array.length; index += 2) 
    { 
    tempSortList[tempIndex] = merge(array[index], array[index + 1]); 
    if (tempIndex != tempSortList.length) 
    { 
     tempIndex++; 
    } 
    } 
    array = tempSortList; 
    return array; 
} 

private static int[] mergeOdd(int[][] array) 
{ 
    /** 
    * The concept is to call the even merge method on the even part 
    * of the list and then once I get to one array, I merge that array 
    * with the extra array. 
    */ 
    int[][] localArray = new int[array.length - 1][1]; 
    int[][] extra = new int[1][1]; 

    for (int index = 0; index < localArray.length; index++) 
    { 
    localArray[index][0] = array[index][0]; 
    } 

    extra[0][0] = array[array.length - 1][0]; 

    int[][] tempSortList = new int[localArray.length/2][]; 
    int tempIndex = 0; 
    for (int index = 0; index < localArray.length; index += 2) 
    { 
    tempSortList[tempIndex] = merge(localArray[index], localArray[index + 1]); 
    if (tempIndex != tempSortList.length) 
    { 
     tempIndex++; 
    } 
    } 
    localArray = tempSortList; 

    return localArray[0] = merge(localArray[0], extra[0]); 
} 

這是很自我解釋，但以防萬一。上面的方法排序不同，因爲數組是奇數還是偶數。最後，這些方法調用實際的合併方法（工作我認爲）：

/** 
* A merge method to merge smaller arrays to bigger 
* arrays 
* @param arrayOne The first array being fed in 
* @param arrayTwo The second array being fed in 
* @return A new integer array which is the sum of the 
* length of the two arrays 
*/ 
private static int[] merge(int[] arrayOne, int[] arrayTwo) 
{ 
    /* 
    * To make a proper method that deals with odd array sizes 
    * look into seeing if it odd, only merging length of the array -1 
    * and then once that is all merged merge that array with the last part of the array 
    */ 
    //Creating the size of the new subarray 
    int[] mergedArray; 

    if (arrayOne.length % 2 == 0 && arrayTwo.length % 2 == 0) 
    { 
    int size = arrayOne.length; 
    int doubleSize = 2 * size; 
    mergedArray = new int[doubleSize]; 

    //Positions of each array 
    int posOne = 0; 
    int posTwo = 0; 
    int mergeIndex = 0; 

    while (posOne < size && posTwo < size) 
    { 
     if (arrayOne[posOne] < arrayTwo[posTwo]) 
     { 
      mergedArray[mergeIndex] = arrayOne[posOne]; 
      mergeIndex++; 
      posOne++; 
     } 
     else 
     { 
      mergedArray[mergeIndex] = arrayTwo[posTwo]; 
      mergeIndex++; 
      posTwo++; 
     } 
    } 

    if (posOne == size) 
    { 
     for (int rest = posTwo; rest < size; rest++) 
     { 
      mergedArray[mergeIndex] = arrayTwo[rest]; 
      mergeIndex++; 
     } 
    } 
    else 
    { 
     for (int rest = posOne; rest < size; rest++) 
     { 
      mergedArray[mergeIndex] = arrayOne[rest]; 
      mergeIndex++; 
     } 
    } 

    } 
    else 
    { 
    int arrayOneSize = arrayOne.length; 
    int arrayTwoSize = arrayTwo.length; 
    int newArraySize = arrayOneSize + arrayTwoSize; 
    mergedArray = new int[newArraySize]; 

    //Position in each array 
    int posOne = 0; 
    int posTwo = 0; 
    int mergeIndex = 0; 

    while (posOne < arrayOneSize && posTwo < arrayTwoSize) 
    { 
     if (arrayOne[posOne] < arrayTwo[posTwo]) 
     { 
      mergedArray[mergeIndex] = arrayOne[posOne]; 
      mergeIndex++; 
      posOne++; 
     } 
     else 
     { 
      mergedArray[mergeIndex] = arrayTwo[posTwo]; 
      mergeIndex++; 
      posTwo++; 
     } 
    } 
    if (posOne == arrayOneSize) 
    { 
     mergedArray[mergeIndex] = arrayTwo[posTwo]; 
     mergeIndex++; 
    } 
    else 
    { 
     for (int rest = posOne; rest < arrayOneSize; rest++) 
     { 
      mergedArray[mergeIndex] = arrayOne[rest]; 
      mergeIndex++; 
     } 
    } 

    } 

    return mergedArray; 
} 

所以我的問題是，它的任何數組的大小我正確送入中，它只能在一定的尺寸。我已經閱讀了一些文章，但是我的實現與我所見過的大多數不同，這就是我在這裏發佈的原因。我不想只是複製一個工作，我想了解我做錯了什麼，所以我可以修復它。預先感謝幫助傢伙！

Answer 1

您的問題在於merge的邏輯。通過使用該行

int size = arrayOne.length; 

您假定兩個數組具有相同的長度。但是，在不均勻的情況下，並非所有陣列都具有相同的長度。

將其改爲兩種不同的尺寸，代碼應該沒問題。

Answer 2

你更大的問題是你的算法太複雜了，更不用說對於非常大的數組了。

我假設你正在做這個學術練習，但是無論何時你得到它的工作，檢查java.util.Arrays.mergeSort（私有方法）爲例。