병합 정렬(Merge Sort)

비교연산과 이동연산이 실제 정렬을 진행하는 MergeTwoArea 함수를 중심으로 진행되기 때문에, MergeTwoArea 함수를 기준으로 계산합니다. 정렬의 대상인 데이터의 수가 n개 일 때, 각 병합의 단계마다 최대 n번의 비교연산이 진행됩니다. 즉, 병합 정렬의 비교 연산과 이동연산의 빅오는 nlong(2)n 으로 정리가 됩니다. 참고로 병합 정렬에는 임시 메모리가 필요하다는 단점이 있습니다.

#include <stdio.h>
#include <stdlib.h>
 
void MergeTwoArea(int arr[], int left, int mid, int right) {
    int fIdx = left;
    int rIdx = mid + 1;
    int i;
 
    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++];
 
        sIdx++;
    }
 
    if (fIdx > mid) {
        for (i = rIdx; i <= right; i++, sIdx++) {
            sortArr[sIdx] = arr[i];
        }
    }
    else {
        for (i = fIdx; i <= mid; i++, sIdx++) {
            sortArr[sIdx] = arr[i];
        }
    }
 
    for (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);
    }
}
 
int main(void) {
    int arr[] = { 3,2,4,1,7,6,5 };
    int i;
 
    MergeSort(arr, 0, sizeof(arr) / sizeof(int) - 1);
    for (i = 0; i < 7; i++)
        printf("%d ", arr[i]);
    printf("\n");
    return 0;
}