Ist das MergeSort?

Question

Ich habe versucht, MergeSort zu codieren. Aber mein Code sieht sehr anders aus als bekannte Implementierungen von MergeSort. Also würde ich gerne wissen, ob meine Implementierung korrekt ist. Mein Algorithmus nimmt zwei int-Arrays (jedes ist sortiert) und legt sie in ein sortiertes großes Array. Und was ist die asymptotische Komplexität meines Algorithmus? Vielen Dank!!

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

Was Sie haben, ist eine Zusammenführung (keine Merge-Sortierung), die zwei bereits sortierte Arrays zusammenführt. Die Zeitkomplexität ist O (n), wobei n die Summe der Anzahl der Elemente im Array und der Anzahl der Elemente in Array2 ist.