[C언어] 병합정렬 (Merge Sort) 소스 코드

#include <stdio.h> 
#include <stdlib.h>
#define SIZE 10
 
void merge(int arr[], int start1, int end1, int start2, int end2)
{
    // 앞 배열의 인덱스와 뒤 배열의 인덱스 
    int i = start1, j = start2;
    
    // 임시 배열 (정렬을 위한)
    int nArrSize = end2 - start1 + 1;
    int index = 0;
    int* pTemp = (int*) malloc(sizeof(int) * nArrSize);
    
    // 두 배열을 오름차순으로 pTemp에 저장 
    while(i <= end1 || j <= end2)
    {
        // 배열 index out of bound 오류 방지 
        if(i > end1)
        {
            *(pTemp + index++) = arr[j++];
        }
        else if(j > end2)
        {
            *(pTemp + index++) = arr[i++];
        }
        else if(arr[i] > arr[j])
        {
            *(pTemp + index++) = arr[j++];
        }
        else
        {
            *(pTemp + index++) = arr[i++];
        }
    }
    
    // pTemp 배열을 본래 arr 배열에 복사
    for(int i = 0; i < nArrSize; i++) 
    {
        arr[start1 + i] = *(pTemp + i);
    }
    
    free(pTemp);
}
 
void mergeSort(int arr[], int start, int end)
{
    // 종료 조건 
    if(start >= end) return;
    
    int nMid = (start + end) / 2;
    
    // 정렬이 된 배열 = 정렬이 된 배열의 절반 2개를 정렬하면서 합친 것이다. 
    mergeSort(arr, start, nMid);
    mergeSort(arr, nMid + 1, end);
    merge(arr, start, nMid, nMid + 1, end);
}
 
int main(void)
{
    int arr[SIZE] = { 2, 1, 4, 3, 10, 7, 8, 6, 9, 5 };
    
    printf("정렬 전 : ");
    for(int i = 0; i < SIZE; i++)
    {
        printf("%d ", arr[i]);
    }
    printf("\n");
    
    mergeSort(arr, 0, SIZE - 1);
    
    printf("정렬 후 : ");
    for(int i = 0; i < SIZE; i++)
    {
        printf("%d ", arr[i]);
    }
    
    return 0;
}

 

임시 배열을 만들어야 된다는 단점을 제외하곤 빠르고 시간이 불규칙하지 않다는 것처럼 장점이 많은 알고리즘인 것 같다. 왠만해서 이 알고리즘을 쓰는 것을 추천한다.

Output:

정렬 전 : 2 1 4 3 10 7 8 6 9 5
정렬 후 : 1 2 3 4 5 6 7 8 9 10