[알고리즘] 병합 정렬(Merge Sort)

병합 정렬은 합병 정렬이라고도 불리며 존 폰노이만이 개발하였습니다.

퀵 정렬과 같이 분할 정복 알고리즘의 하나입니다.

 

[병합 정렬의 과정]

1. 리스트의 길이가 0 또는 1이면 이미 정렬된 것으로 본다.

2. 그렇지 않은 경우에는 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다.

3. 각 부분 리스트를 재귀적으로 병합 정렬을 이용해 정렬한다.

4. 두 부분 리스트를 다시 하나의 정렬된 리스트로 병합한다.

병합정렬(합병 정렬)

병합 정렬에 대해 조금 더 쉽게 설명하자면

1. 먼저 분할 과정을 통해 리스트에 원소가 1개 남을 때까지 분할을 합니다.

2. 새로운 리스트에 2개의 리스트를 비교해가며 작은 값을 넣어줍니다.

3. 둘 중에 하나가 끝날 때까지 반복합니다.

4. 하나가 먼저 끝나면 나머지 리스트에 남은 값들을 넣어줍니다.

5. 새로운 리스트를 원래 있던 리스트로 옮겨줍니다.

1(devide) / 2, 3, 4, 5(merge)

 

[병합 정렬 시간 복잡도]

병합 정렬은 배열의 너비가 N이고 단계의 크기가 logN이 나와 시간 복잡도는 NlogN이 나옵니다.

병합 정렬은 worst, average, best 모두 NlogN이 나오는 빠르면서 안정적인 정렬 알고리즘입니다.

 

[C언어 코드]

#include <stdio.h>
int sorted[10];    //나눈 리스트들을 정렬하여 저장할 배열
 
void merge(int a[], int low, int middle, int high)
{
    int i = low;
    int j = middle + 1;
    int k = low;
    //왼쪽에 있는 배열은 처음부터 중간까지 검사하고 
    //오른쪽에 있는 배열은 중간 + 1부터 끝까지 검사
    while (i <= middle && j <= high)
    {
        //둘중에 작은 것을 먼저 전역 배열에 넣음
        if (a[i] <= a[j])
        {
            sorted[k] = a[i];
            i++;
        }
        else
        {
            sorted[k] = a[j];
            j++;
        }
        k++;
    }
    //위에 검사에서 i 나 j 중에 먼저 끝나는 것이 있을 수도 있으므로
    //남아 있는 것들을 넣어줌
    //i가 미들보다 크다면 왼쪽이 먼저 다 들어간 것이므로 j부터 high까지 다 넣어줌
    if (i > middle)
    {
        for (int t = j; t <= high; t++)
        {
            sorted[k] = a[t];
            k++;
        }
    }
    //else의 경우는 i가 다 끝나지 않았는데 반복문을 빠져나온 것이므로
    //j는 다 끝난 경우임 따라서 i부터 middle까지 넣어줌
    else
    {
        for (int t = i; t <= middle; t++)
        {
            sorted[k] = a[t];
            k++;
        }
    }
 
    //정렬된 배열을 삽입
    for (int t = low; t <= high; t++)
    {
        a[t] = sorted[t];
    }
}
 
void mergeSort(int a[], int low, int high)
{
    //크기가 1보다 큰 경우
    if (low < high)
    {
        int middle = (low + high) / 2;
        //먼저 왼쪽과 오른쪽으로 반반으로 나누고
        mergeSort(a, low, middle);
        mergeSort(a, middle + 1, high);
        //나중에 합친다
        merge(a, low, middle, high);
    }
    else
    {
        return;
    }
}
 
int main()
{
    int arr[10] = { 1, 5, 7, 9, 2, 3, 6, 4, 0, 8 };
 
    mergeSort(arr, 0, 9);
 
    for (int i = 0; i < 10; i++)
    {
        printf("%d ", arr[i]);
    }
 
    return 0;
}