잘못된 병합 출력

Question

C++의 템플릿 함수를 사용하여 병합 정렬 알고리즘을 작성하려고합니다. 출력은 가깝지만 올바르지 않습니다. 나는 구체적으로 문제가 병합 정렬 함수가 아니라 병합 함수에 있다고 생각한다. 어떤 도움이라도 대단히 감사 할 것입니다.

이

template <class T1> 
void mergeSort(T1 array[], int lower, int upper) 
{ 
    if (lower < upper) 
    { 
     int middle = (lower + upper)/2; 

     mergeSort(array, lower, middle); 
     mergeSort(array, middle + 1, upper); 
     merge(array, lower, middle, upper); 
    } 
} 

template <class T1> 
void merge(T1 array1[], int lower, int middle, int upper) 
{ 
    int i = 0, 
     j = 0, 
     k = 0; 
    int size1 = middle - lower + 1; 
    int size2 = upper - middle; 
    T1* temp1 = new T1[size1]; 
    T1* temp2 = new T1[size2]; 

    for (int i = 0; i < size1; i++) 
    { 
     temp1[i] = array1[lower + i]; 
    } 
    for (int j = 0; j < size2; j++) 
    { 
     temp2[j] = array1[middle + 1 + j]; 
    } 

    while (i < size1 && j < size2) 
    { 
     if (temp1[i] < temp2[j]) 
     { 
      array1[k] = temp1[i]; 
      i++; 
     } 
     else 
     { 
      array1[k] = temp2[j]; 
      j++; 
     } 
     k++; 
    } 

    if (i == size1) 
    { 
     while (j < size2) 
     { 
      array1[k] = temp2[j]; 
      k++; 
      j++; 
     } 
    } 
    else 
    { 
     while (i < size1) 
     { 
      array1[k] = temp1[i]; 
      k++; 
      i++; 
     } 
    } 
} 

int main(){ 
    int a[] = { 7, 6, 4, 8, 1, 2, 3 }; 
    mergeSort(a, 0, 6); 
} 

출력 :이 잘못된 위치에 병합의 결과를 기록합니다 때문에 merge 기능에

1 1 2 2 3 3 8 

Answer 1

0으로 k를 초기화하지 않아야 여기 내 코드입니다. 대신 k을 lower으로 초기화해야합니다. 그것이 실제로 정렬하는 파트의 시작 인덱스이기 때문입니다.