[백준/BOJ] 2751번 수 정렬하기 2 (C++)

www.acmicpc.net/problem/2751

2751번: 수 정렬하기 2

병합 정렬을 이용하여 문제를 해결했습니다.

 

#include <iostream>
using namespace std;

int a[1000001];
int tmp[1000001];

void divide(int lt, int rt) {
    if(lt < rt) {
        int mid = (lt + rt) / 2;
        divide(lt, mid);
        divide(mid + 1, rt);
        int p1 = lt, p2 = mid + 1, p3 = lt;
        
        while(p1 <= mid && p2 <= rt) {
            if(a[p1] <= a[p2]) tmp[p3++] = a[p1++];
            else tmp[p3++] = a[p2++];
        }
        
        while(p1 <= mid) {
            tmp[p3++] = a[p1++];
        }
        
        while(p2 <= rt) {
            tmp[p3++] = a[p2++];
        }
        
        for(int i = lt; i <= rt; i++) {
            a[i] = tmp[i];
        }
    }
}

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
    int n;
    cin >> n;
    
    for(int i = 0; i < n; i++) {
        cin >> a[i];
    }
    
    divide(0, n - 1);
    
    for(int i = 0; i < n; i++) {
        cout << a[i] << "\n";
    }
}