[Algorithm] Merge Sort

 

소스코드

#include <cstdio>
#include <algorithm>

using namespace std;

const int MX = 50001;

int a[MX];

void merge(int *a, int left, int mid, int right)
{
    int tmp[MX], pos = left;
    int u = left, v = mid+1;

    while (u <= mid && v <= right) {
        if (a[u] <= a[v]) {
            tmp[pos++] = a[u++];
        }
        else {
            tmp[pos++] = a[v++];
        }
    }

    while (u <= mid) {
        tmp[pos++] = a[u++];
    }

    while (v <= right) {
        tmp[pos++] = a[v++];
    }

    for (int i = left; i <= right; ++i) {
        a[i] = tmp[i];
    }
}

void merge_sort(int *a, int l, int r)
{
    if (l >= r) return;

    int mid = (l + r) / 2;
    merge_sort(a, l, mid);
    merge_sort(a, mid + 1, r);
    merge(a, l, mid, r);
}

int main()
{
    int n, a[MX];
    scanf("%d", &n);
    for (int i = 0; i < n; ++i)
        scanf("%d", &a[i]);

    merge_sort(a, 0, n - 1);
    for (int i = 0; i < n; ++i) {
        printf("%d ", a[i]);
    }
    return 0;
}

 

 

 

 

 

공부한 것을 정리하기 위한 기록입니다.

틀린 부분이 있다면 부드럽게 알려주세요.