Это 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.