[ Algorithm ] MergeSort

오늘은 합병정렬에 대해 얘기해보려고 합니다.

그게 뭐죠?

합병정렬(Merge Sort)는 분할정복 기법을 기반으로한 정렬기법입니다.
시간복잡도는 O(n*log(n))만큼 걸립니다.

그래서 어떻게 하나요?

총 3단계에 걸쳐서 합병정렬이 일어납니다.
분할: 입력 배열을 같은 크기의 2개의 부분 배열로 분할합니다.
정복: 원래 배열 수와 맞을 때까지 부분배열을 정렬합니다.
결합: 정렬된 부분배열을 하나의 배열에 통합합니다.

음.. 정렬을 어떻게..?

Q: 분할은 뭐 2개씩 사이즈 쪼개면서 하니까 알겠는데 정렬은 뭐 어떻게 하나요?
A
1. A배열과 B배열의 각각 첫번째 원소의 위치를 i, j로 넣습니다.
2. i랑 j를 계속 이동하면서 작은 원소를 정렬할 배열에 넣습니다.

Code

#include <stdio.h>
int sorted[100],count;
void merge(int list[], int left,int mid, int right)
{
    int i,j,k,l;
    i=left;
    j=mid+1;
    k=left;
    while(i<=mid && j<=right)
    {
        if(list[i]<=list[j])
        {
            sorted[k++]=list[i++];
        }
        else
        {
            sorted[k++]=list[j++];
        }
    }
    if(i>mid)
    {
        for(l=j; l<=right; l++)
        {
            sorted[k++]=list[l];
        }
    }
    else
    {
        for(l=i; l<=mid; l++)
        {
            sorted[k++]=list[l];
        }
    }
    for(l=left; l<=right; l++)
    {
        list[l]=sorted[l];
    }
}
void mergesort(int list[], int left,int right)
{
    int mid;
    if(left<right)
    {
        mid=(left+right)/2;
        mergesort(list,left,mid);
        mergesort(list,mid+1,right);
        merge(list,left,mid,right);
    }
}
int main()
{
    int list[4]={27,12,20,25};
    mergesort(list,0,3);
    for(int i=0; i<4; i++)
    {
        printf("%d ",list[i]);
    }
    return 0;
}