有一种工作合并排序，但不完全，有人可以告诉我我做错了什么？

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（私有方法）为例。