[삼성 알고리즘] Merge 알고리즘

1. 구현

Merge 알고리즘은 O(N log N)으로 정렬하는 이론상 가장 효율적인 정렬 알고리즘이다.

구현방법은 우선 숫자들을 모두 잘게 쪼갠 뒤 합쳐지는 과정에서 비교를 통해 정렬을 진행하며 합치는 과정이다.

이 때 N개의 원소에 대하여 총 트리의 높이는 logN 값을 가지기 때문에 효율적인 연산이 가능해진다.

 

2. 알고리즘

- 백준(수 정렬하기 2)

 

#include <iostream>

using namespace std;

int prior[1000001];
int after[1000001];

void merge(int L, int R, int mid) {
int i = L;
int j = mid + 1;
int k = i;

while (i <= mid && j <= R) {
if (prior[i] > prior[j]) {
after[k++] = prior[j++];
}
else {
after[k++] = prior[i++];
}
}
while (i <= mid) {
after[k++] = prior[i++];
}
while (j <= R) {
after[k++] = prior[j++];
}

for (int i = L; i <= R; i++) {
prior[i] = after[i];
}
}
void divide(int L, int R) {
if (L >= R) {
return;
}
int mid = (L + R) / 2;
divide(L, mid);
divide(mid + 1, R);
merge(L, R, mid);
}
int main(void) {

cin.tie(0);
ios::sync_with_stdio(false);
int N;
cin >> N;
for (int i = 0; i < N; i++) {
int buf;
cin >> buf;
prior[i] = buf;
}
after[0] = prior[0];
divide(0, N - 1);

for (int i = 0; i < N; i++) {
cout << after[i] << "\n";
}
return 0;
}