합병정렬

Array를 반씩 쪼갠다.

한번 쪼개면 두개의 큰 덩어리가 나올 것이다.

이렇게 나온 덩어리를 또 다시 쪼갠다.

이렇게 덩어리를 계속 쪼개다 보면, 결국 한 개의 원소가 하나의 덩어리가 된다.

이 상태에서 다시 덩어리를 뭉치는데, 그냥 뭉치는 것이 아니라

각각의 원소를 비교해 가면서 원소를 차례로 배열한다.

이런 식으로 덩어리를 계속 뭉쳐가다 보면 원래의 Array가 정렬된다.

이것이 합병 정렬의 기본 아이디어다.

코드

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56

#include <stdio.h> #define LEN 9   void merge_sort(int num[],int start, int end);  void merge(int num[], int start, int mid, int end); void tracer(int num[],int len);   int main(void){            int testArr[LEN] = {485,241,454,325,452,685,498,890,281};     merge_sort(testArr, 0, LEN-1); }   void merge_sort(int num[],int start, int end){ // Array를 두개의 덩어리로 나눔     int median = (start + end)/2; // 중간값 설정     if(start < end){ // 덩어리의 원소가 하나일 때까지         merge_sort(num, start, median);          merge_sort(num, median+1, end); // 각각의 덩어리로 재귀함수 호출          merge(num, start, median, end); // 각각의 덩어리를 뭉치면서 정렬     } }   void merge(int num[], int start, int median, int end){     int i,j,k,m,n;     int tempArr[LEN]; // 임시로 데이터를 저장할 배열     i = start; // 앞의 덩어리의 시작 Index     j = median+1; // 뒤의 덩어리의 시작 Index     k = start; // 임시 배열의 시작 Index       while (i <= median && j <= end){         tempArr[k++] = (num[i] > num [j]) ? num [j++] : num [i++];         //작은 숫자를 찾아 임시 배열에 넣는다. 어느쪽 덩어리든 Index의 끝에 닿으면 빠져나온다.     }            // 아직 배열에 속하지 못한 부분들을 넣기 위한 부분     m = (i > median) ? j : i; // 아직 원소가 남아있는 덩어리가 어디인지 파악     n = (i > median) ? end : median; // 마찬가지로, for문의 끝 Index를 정하기 위함임       for (; m<=n; m++){ // 앞에서 구한 m, n으로 배열에 속하지 못한 원소들을 채워넣음         tempArr[k++] = num[m];     }       for (m=start; m<=end; m++){         num[m] = tempArr[m]; // 임시 배열에서 원래 배열로 데이터 옮기기     }     printf("Merging: %d ~ %d & %d ~ %d\n",start,median,median+1,end);     tracer(num,LEN); }   void tracer(int num[],int len){     int i;     for(i=0;i<len;i++){         printf("%d\t",num[i]);     }     printf("\n\n"); }

결과

분석

위에서 9개의 원소를 가진 배열의 인덱스를 각각 0 ~ 8 이라고 했을때,

다음과 같은 덩어리로 나뉘어진다.

(((0, 1), 2), (3, 4)), ((5, 6), (7, 8))

결과에서 표시하고 있는 것은 이렇게 나뉘어진 원소들의 Index와 병합한 이후의 Array라고 할 수 있다.