머지소트(merge sort)

Merge sort은 'divide and conquer(분할정복)'의 대표적인 알고리즘이다.

분할 정복 알고리즘(Divide and conquer algorithm)은 그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 방법이나 알고리즘이다.
(출처: https://ko.wikipedia.org/wiki/%EB%B6%84%ED%95%A0_%EC%A0%95%EB%B3%B5_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

분할 정복 알고리즘 - 위키백과, 우리 모두의 백과사전

 

merge sort는 다음 3가지 단계로 동작한다.

분할(Divide): 입력 배열을 2개의 부분 배열로 분할한다.
정복(Conquer): 부분 배열을 정렬한다. 
결합(Combine): 정렬된 부분 배열들을 하나의 배열에 합병(merge)한다.

 

1. 분할

2.정복 & 결합

 

 

코드로 구현해 보면 다음과 같다.

#include <stdio.h>

int arr[8] = { 1, 3, 2, 7, 8, 5, 6, 4};
int temp[8];

void merge_sort(int start, int end)
{       
        int mid = (start + end) / 2;
        
        if (start >= end)
                return;
        
        merge_sort(start, mid);
        merge_sort(mid + 1, end);
        
        int a = start;
        int b = mid + 1;
        int c = 0;
        
        while (1) {
                if (a == mid + 1 && b == end + 1)
                        break;
                
                if (a == mid + 1) 
                        temp[c++] = arr[b++];
                else if (b == end + 1) 
                        temp[c++] = arr[a++];
                else if (arr[a] < arr[b]) 
                        temp[c++] = arr[a++];
                else    
                        temp[c++] = arr[b++];
        }
        
        for(int i = 0; i < c; i++)
                arr[start + i] = temp[i];
}

void print()
{
        for (int i = 0; i < sizeof(arr) / sizeof(int); i++)
                printf("%d ", arr[i]);
        printf("\n");
}
int main()
{
        print();
        merge_sort(0, 7);
        print();

        return 0;
}