합병 정렬(Merge Sort)

간단한 합병정렬이다.

void merge(int a[], int b[], int low, int mid, int high){
 int i, l, m, k;
 l = low;
 m = mid + 1;
 k = low;
 while (l <= mid && m <= high){
  if (a[l] <= a[m]){
   b[k++] = a[l++];
  }
  else
   b[k++] = a[m++];
 }
 if (l>mid)
  for (i = m; i <= high; i++)
   b[k++] = a[i];
 else
  for (i = l; i <= mid; i++)
   b[k++] = a[i];
}

void merge_sort(int a[], int b[], int low, int high){
 int mid;
 if (low<high){
  mid = (low + high) / 2;
  merge_sort(a, sorted, low, mid);
  merge_sort(a, sorted, mid + 1, high);
  merge(a, sorted, low, mid, high);
 }
}