이 MergeSort입니까?

Question

MergeSort를 코딩하려고했습니다. 그러나 제 강령은 MergeSort의 유명한 구현과 매우 다릅니다. 그래서 내 구현이 정확한지 알고 싶습니다. My Algorithm은 두 개의 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은 array의 요소 수 + array2의 요소 수입니다.