7. Merge sort(합병정렬)

덩어리를 최소화 해 각 1개까지 쪼갠 뒤,

다시 합치는 방식이다.

Quick sort처럼 O(n logn)의 시간복잡도를 가진다.

하지만, Quick sort 마냥 O(n^2)의 시간복잡도까지 가지도 않는다.

최악의 상황에도 O(n log n)을 가지게 된다.

#include <iostream>
#define __size__ 9
 
using namespace std;
 
int sort_array[__size__];
 
void merge(int arr[], int left, int mid, int right) {
    int i, j, k, l;
    i = left;
    j = mid+1;
    k = left;
    while(i<=mid && j<=right){
      if(arr[i]<=arr[j]) sort_array[k++] = arr[i++];
      else sort_array[k++] = arr[j++];
    }
    if(i>mid) for(l=j; l<=right; l++) sort_array[k++] = arr[l];
    else for(l=i; l<=mid; l++) sort_array[k++] = arr[l];
    for(l=left; l<=right; l++) arr[l] = sort_array[l]; 
}
 
void merge_sort(int arr[], int left, int right){
  int mid;
  if(left < right){
    mid=(left + right) / 2;
    merge_sort(arr, left, mid);
    merge_sort(arr, mid+1, right);
    merge(arr, left, mid, right);
  }
}
int main(int argc, char *argv[]){
  int arr[10] = {43,23,10,35,13,53,4,2,63,25};
  int n=10;
  merge_sort(arr, 0, 9);
  for(int i=0; i<n; i++) printf("%02d ",*(arr+i));
  cout << endl;
  return 0;
}