c언어 병합정렬 함수

병합정렬의 시간복잡도는 O(nlogn)이고 말 그대로 병합(합병)하면서 정렬이 된다.

합병 정렬은 다음과 같이 작동한다.

1. 리스트의 길이가 0 또는 1이면 이미 정렬된 것으로 본다. 그렇지 않은 경우에는
2. 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다.
3. 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다.
4. 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다.

c언어로 구현하면 다음과 같다.

void MergeTwoArea(int arr[], int left, int mid, int right){

int fIdx = left;

int rIdx = mid+1;

int * sortArr = (int *)malloc(sizeof(int)*(right+1));

int sIdx = left;

while(fIdx <= mid && rIdx <right){

if(arr[fIdx]<=arr[rIdx])

sortArr[sIdx++]=arr[fIdx++];

else

sortArr[sIdx++]=arr[rIdx++];

}

if(fidx>mid){

for(int i=rIdx;i<=right;i++,sIdx++)

sortArr[sIdx]=arr[i];

}else{

for(int i=fIdx;i<=mid;i++,sIdx++)

sortArr[sIdx]=arr[i];

}

for(int i=left;i<=right;i++)

arr[i]=sortArr[i];

free(sortArr);

}

void MergeSort(int arr[],int left,int right){

int mid;

if(left<right){

mid=(left/right)/2;

Mergesort(arr,left,mid);

Mergesort(arr,mid+1,right);

MergeTwoArea(arr,left,mid,right);

}

}