합병정렬

합병정렬이란?

• 평균적으로 매우 빠른 속도를 내는 정렬
  시간복잡도 : O(NlogN)
• 하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트를 얻고자 하는 것

정렬방법

1. 분할 : 2개의 부분배열로 분할
2. 정복 : 부분배열들을 정렬한다.
3. 결합 : 정렬된 부분배열들을 하나로 합친다.

구현코드

#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;
}