C/C++ 병합정렬(Merge Sort) 코드

병합정렬 위키 링크 

병합정렬은 O(NlogN) 에 시간복잡도를 가진다.

1,000 개의 데이터를 정렬 한다면 1,000 X log1,000 = 1,000 X 10 = 10,000 이다.

만약 1,000,000개의 데이터를 정렬 한다면 1,000,000 X log1,000,000 = 1,000,000 X 20 = 20,000,000 이다.

2천만으로 1ms정도 안에 처리가 가능한 수준이다.

버블 정렬이나 선택정렬 등은 O(N^2) 의 시간 복잡도를 가진다. 

1,000개의 데이터를 정렬 한다면 1,000 X 1,000 = 1,000,000 이 된다.

1,000,000개의 데이터를 정렬 한다면 1,000,000 X 1,000,000 = 1,000,000,000,000 이다.

1조나 되기때문에 1ms에 처리가 불가능 하다.

 

데이터에 숫자가 많으면 버블 정렬에 비해 속도가 엄청 빠르다.

하지만 임시 메모리를 두고 데이터를 복사해야하기 때문에 메모리 사용이 버블 정렬에 비해 크다.

데이터의 갯수가 1,000 개 수준이라면 버블 정렬을 이용해도 되지만 그 이상 만개가 된다면 병합정렬이나 퀵정렬을 고려해보아야 한다.

퀵정렬에 비해 병합정렬은 코드가 간단해서 구현하기가 쉬운편이고 퀵정렬에 비해 속도가 안정적이다.

병합정렬은 데이터를 반씩 쪼개서 반씩 정렬을 하는 방식이다.

4 1 2 3 을 오름차순 정렬 한다고 하면

4 과 1를 정렬하면 1 4 가 되고 

2와 3을 정렬 하면 2 3 이된다.

1 4 와  2 3을 정렬 하는데

각각 앞에서 부터 정렬을 시작한다.

1과 2를 비교하여 1이 작기 때문에 1을 넣고 그다음 4와 2를 비교하여 2가 작기 떄문에 1 2 로 저장하고

4와 3을 비교하여 3이 작기 때문에 1 2 3 이되고 마지막 4를 추가하여 1 2 3 4 가 된다.

모든 경우를 비교하지 않기때문에 속도가 빠르다.

기본적으로 병합정렬은 재귀함수로 구현한다.

반으로 쪼개서 다시 재귀함수로 호출하고

호출한 결과를 가지고 정렬을 한다.

이걸 계속 반복하는 방식이다.

- 바로 쓸 수 있는 병합 정렬(Merge Sort) 코드 오름차순 정렬 -

void mergeSort(int data[], int s, int e) {
    int tmp[10000];
    int i = s;
    int k = s;
    int m = (s + e)/2;
    int j = m + 1;
    if (s >= e) return; //쪼갤수 없음, 되돌아가기
    mergeSort(data, s, m); //분할
    mergeSort(data, m+1, e); //분할
    while ((i <= m) && (j <= e)) { //병합
        if (data[i] < data[j]) tmp[k++] = data[i++];
        else tmp[k++] = data[j++];
    }
    while (i <= m) tmp[k++] = data[i++]; //나머지 병합
    while (j <= e)  tmp[k++] = data[j++]; //나머지 병합
    for (i = s; i <= e; i++) data[i] = tmp[i]; //복사
}

---

- 실제 사용 예제 -

#include<stdio.h>
void mergeSort(int data[], int s, int e) {
    int tmp[10000];
    int i = s;
    int k = s;
    int m = (s + e) / 2;
    int j = m + 1;
    if (s >= e) return; //쪼갤수 없음, 되돌아가기
    mergeSort(data, s, m); //분할
    mergeSort(data, m + 1, e); //분할
    while ((i <= m) && (j <= e)) { //병합
        if (data[i] < data[j]) tmp[k++] = data[i++];
        else tmp[k++] = data[j++];
    }
    while (i <= m) tmp[k++] = data[i++]; //나머지 병합
    while (j <= e)  tmp[k++] = data[j++]; //나머지 병합
    for (i = s; i <= e; i++) data[i] = tmp[i]; //복사
}
 
int main() {
    int data[] = { 1,5,2,4,3,7,-1,10,6 };
    mergeSort(data, 0, sizeof(data) / sizeof(int)-1);
    for (int i = 0; i < sizeof(data) / sizeof(int); i++) {
        printf("%d ", data[i]);
    }
    printf("\n");
}