[정렬 알고리즘] Merge Sort(병합 정렬)

§Merge Sort

배열을 절반으로 두개의 서브 배열로 나누는걸 서브 배열의 원소가 한개가 될때까지 반복한 후 정렬 하며 다시 병합하는 알고리즘

 

 

mergeSort(arr[], 1, r)

If r > 1:

1. 배열을 나눌 중간점을 구한다 : middle m = (1+r)/2
2. mergeSort(arr, 1, m)을 호출한다.
3. mergeSort(arr, m+1, r)을 호출한다.
4. 두개의 정렬되어 반으로 나누어진 배열을 합병한다 : merge(arr, 1, m, r)

 

 

 

Time Complexity : O(n*logn) //T(n) = 2T(n/2) +O(n)

Auxiliary Space: O(n)

 

 

언어 ( C )

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 57 58 59 60 61 62 63 64

//////////////////////////////// //    Merge Sort //    병합 정렬 ////////////////////////////////   #include <stdio.h> #define arSIZE 7   void merge(int arr[], int s, int m, int d) {     int arTmp[arSIZE];     int i, j, k;     i = s;     j = m + 1;     k = s;       while (i <= m && j <= d) {         if (arr[i] <= arr[j]) {             arTmp[k] = arr[i];             i++;         }         else {             arTmp[k] = arr[j];             j++;         }         k++;     }       if (i > m) {         for (j; j <= d; j++, k++)             arTmp[k] = arr[j];     }     else {         for (i; i <= m; i++, k++)             arTmp[k] = arr[i];     }       for (int n = s; n <= d; n++)         arr[n] = arTmp[n]; }   void mergeSort(int arr[], int s, int d) {     if (s < d) {         int m = (s + d) / 2;         mergeSort(arr, s, m);         mergeSort(arr, m + 1, d);         merge(arr, s, m, d);     } }   void printArray(int arr[], int size) {     int i;     for (i = 0; i < size; i++)         printf("%d ", arr[i]);     printf("\n"); }   int main() {     int arr[] = { 12, 11, 13, 5, 6, 7, 10 };       mergeSort(arr, 0, arSIZE - 1);     printf("Sorted array : ");     printArray(arr, arSIZE);     return 0; } Colored by Color Scripter

cs