[Jungol] 정올 3519 Tutorial : 합병(병합)정렬(Merge Sort)

출처: http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=2859&sca=3010

Approach

▶ 합병 정렬(Merge Sort)  

합병 정렬(Merge Sort)

---

#include <stdio.h>
#define LM 500005
 
int N, arr[LM], copyArr[LM];
 
void input() {
    scanf("%d", &N);
    for (int i = 0; i < N; ++i) {
        scanf("%d", arr + i);
    }
}
 
void mergeSort(int* arr, int start, int end) {
    // 0. base condition
    if (start >= end) return;
 
    // 1. divide
    int mid = (start + end) / 2;
    // 2. conquer
    mergeSort(arr, start, mid);
    mergeSort(arr, mid + 1, end);
 
    // 3. merge
    int i = start, j = mid + 1, k = start;
    while (i <= mid && j <= end) {
        if (arr[i] < arr[j]) copyArr[k++] = arr[i++];
        else {
            copyArr[k++] = arr[j++];
        }
    }
 
    while (i <= mid) copyArr[k++] = arr[i++];
    while (j <= end) copyArr[k++] = arr[j++];
 
    // 4. copy
    for (i = start; i <= end; ++i) {
        arr[i] = copyArr[i];
    }
 
    for (i = 0; i < N; ++i) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}
 
int main() {
    input();
    mergeSort(arr, 0, N - 1);
    return 0;
}