非递归O（N）空间合并排序

Question

我正在编码Java中的非递归合并排序算法0​​我必须确定此方法是否作为非递归以及空间复杂度应该是O（N ）

指令我得到了：您可以使用O（N）空间（除了输入数组），并且您的算法应该具有与递归合并排序相同的运行时间。

这是我的代码。

我想确保递归以及O（N）空间 如果有更好的方法，请让我知道。

private static void merge(Integer[] a, Integer[] tmpArray, int leftPos, int rightPos, int rightEnd) { 
     int leftEnd = rightPos - 1; 
     int tmpPos = leftPos; 
     int numElements = rightEnd - leftPos + 1; 

     // Main loop 
     while(leftPos <= leftEnd && rightPos <= rightEnd) { 
      if(a[leftPos] <= a[rightPos ]) { 
       tmpArray[tmpPos++] = a[leftPos++]; 
      } else { 
       tmpArray[tmpPos++] = a[rightPos++]; 
      } 
     } 

     while(leftPos <= leftEnd) { // Copy rest of first half 
      tmpArray[tmpPos++] = a[leftPos++]; 
     } 

     while(rightPos <= rightEnd) { // Copy rest of right half 
      tmpArray[tmpPos++] = a[rightPos++]; 
     } 

     // Copy tmpArray back 
     for(int i = 0; i < numElements; i++, rightEnd--) { 
      a[rightEnd] = tmpArray[rightEnd]; 
     } 
    } 

    public static void mergeSortB(Integer[] inputArray) { 

    Integer[] tempArray = new Integer[inputArray.length]; 

    for(int i = 1; i<inputArray.length; i=i*2) { 
     for(int j=i; j<inputArray.length; j=j+i*2) { 
     int k = j+i-1; 
     if(inputArray.length<j + i) { 
      k = inputArray.length -1; 
     } 
     //call the merge method(non recursive) 
     merge(inputArray, tempArray, j-i,j, k); 
     } 
    } 

    } 

Answer 1

您的代码看起来没问题。虽然，您可以创建一个测试（并在必要时进行调试）以确保您的代码正常工作。 但合并排序有Big(O)== NlogN，而不是N.