[알고리즘] 병합정렬(머지소트/Merge Sort)

int arr[10];
int sorted[10];

mergesort(int arr[], int left, int right){
    // left가 right보다 작으면 계속 반씩 나눠준다. 크다면 아무런 동작도 하지 않고 빠져 나와 재귀함수의 merge부분으로 들어간다.
    if(left < right) {
        int mid = (left+right)/2;
        
        mergesort(arr, left, mid);
        mergesort(arr, mid+1, right);
        merge(arr, left, mid, right); // 반씩 나눈 부분을 합친다.
    }    
}

merge(int arr[], int left, int mid, int right){
    int i = left, j = mid+1, k = left;
    // 나눈 부분을 합친다
    while(i <= mid && j <= right) {
        if(arr[i] < arr[j]) {
            sorted[k] = arr[i];
            i++;
        } else {
            sorted[k] = arr[j];
            j++;
        }
        k++;
    }
    // 왼쪽 부분이 먼저 끝날수도, 오른쪽 부분이 먼저 끝날수도 있기 때문에 남아있는 원소를 넣어준다.
    if(i > mid) {
        for(; j <= right; j++) {
            sorted[k] = arr[j];
            k++;
        }
    } else {
        for(; i <= mid; i++) {
            sorted[k] = arr[i];
            k++;
        }
    }
    // 최종적으로 sorted배열에 있는 원소를 실제 배열인 arr로 옮겨준다
    for(int m = left; m <= right; m++) {
        arr[m] = sorted[m];
    }
}