這是MergeSort？

Question

我試着編碼MergeSort。但是我的代碼與着名的MergeSort實現看起來很不一樣。所以我想知道，如果我的實施是正確的。我的算法需要兩個int數組（每個都是排序的）並將它們放入一個排序的大數組中。什麼是我算法的漸近複雜性？非常感謝你！！

public static int[] myMergeSort(int[] array, int[] array2) { 
    int[] giveback = new int[array.length + array2.length]; 
    int i = 0; 
    int j = 0; 

    for (int x = 0; x < giveback.length; x++) { 
     if (array[i] >= array2[j]){ 
      giveback[x] = array2[j]; 
      j++; 
     } else { 
      giveback[x] = array[i]; 
      i++; 
     } 

     if (i == array.length) { 
      x++; 
      for (int c = j; c < array2.length; c++) { 
       giveback[x] = array2[c]; 
       x++;  
      } 
      return giveback; 
     } 

     if (j == array2.length) { 
      x++; 
      for (int b = i; b < array.length; b++){ 
       giveback[x] = array[b]; 
       x++; 
      } 
      return giveback; 
     } 
    } 

    return giveback; 
} 

Answer 1

你有什麼是合併（而不是合併排序）合併兩個已排序的數組。時間複雜度是O（n），其中n是數組中元素的數量+數組2中元素的數量之和。