Нерекурсивная O(N) космическая сортировка слиянием

Question

Я кодирую нерекурсивный алгоритм сортировки слиянием в Java. Я должен убедиться, что этот метод работает как нерекурсивный, а сложность пространства должна быть 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

Ваш код выглядит хорошо. Хотя вы можете создать тест (и при необходимости отладить), чтобы убедиться, что ваш код работает. Но Merge Sort имеет Big(O)== NlogNне Н.