합병 정렬(Merge Sort)

합병 정렬 - 주어진 배열의 원소가 하나가 될 때까지 배열을 2개로 분할 후 합치면서 정렬하는 알고리즘.

합병정렬의 단점

• 시간복잡도가 O(n logn)이라서 n이 커져도 성능이 보장된다.

합병정렬의 단점

• 임시 하위 배열에 저장하기에 추가공간이 필요해 메모리가 제한된 환경에서는 적합하지 않다.

예시

C언어 구현

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