// MergeSort.cpp : Defines the entry point for the console application.
//

#include “stdafx.h”
#include <stdio.h>
#include <math.h>

#define MAX_NUMBER_OF_DATA 50

void
MergeSort (int _Data[], int _Temp[], int First, int Mid, int Last);

/* Divide Recursivly */
void
Divide (int _Data[], int _Temp[], int First, int Last)
{
  /* if data list’s length is longer than 1 */
  /* In advance, Merge Sort divide elements shorter than pre-defined size. */
  if (First < Last) {
    int Mid = (First + Last) / 2;

    /* For the first part */
    Divide (_Data, _Temp, First, Mid);
    /* For the second part */
    Divide (_Data, _Temp, (Mid + 1), Last);
    /* Sort first and second part */
    MergeSort (_Data, _Temp, First, Mid, Last);
  }
}

void
MergeSort (int _Data[], int _Temp[], int First, int Mid, int Last)
{
  int h = First, i = First;
  int j = Mid + 1;
  int k;

  while ((h <= Mid) && (j <= Last)) {
    /* First Part’s element is selected to insert */
    if (_Data[h] <= _Data[j]) {
      _Temp[i] = _Data[h++];
    }
    /* Second Part’s element is selected to insert */
    else {
      _Temp[i] = _Data[j++];
    }
    i++;
  }

  /* Second Part’s elements are remained without insertion */
  if (h > Mid) {
    for (k=j; k<=Last; k++) {
      _Temp[i++] = _Data[k];
    }
  }
  /* First Part’s elements are remained without insertion */
  else {
    for (k=h; k<=Mid; k++) {
      _Temp[i++] = _Data[k];
    }
  }
  /* Copy sorted data */
  for (k=First; k<=Last; k++) {
    _Data[k] = _Temp[k];
  }
}

int _tmain(int argc, _TCHAR* argv[])
{
  int _Datas[MAX_NUMBER_OF_DATA] = {0};
  int _Temp_Bucket[MAX_NUMBER_OF_DATA] = {0};
  int i, breath;

  for(i=0; i<MAX_NUMBER_OF_DATA; i++){
    _Datas[i] = rand();
  }

  printf(“Datas in bucket before Sorting!! \n”);
  for(i=0; i<MAX_NUMBER_OF_DATA; i++){
    printf(“%d\n”, _Datas[i]);

    if (i%10 == 9) { printf(“\n”); }
  }

  Divide(_Datas, _Temp_Bucket, 0, (MAX_NUMBER_OF_DATA-1));

  printf(“Datas in bucket after Sorting!! \n”);
  for(i=0; i<MAX_NUMBER_OF_DATA; i++){
    printf(“%d\n”, _Datas[i]);

    if (i%10 == 9) { printf(“\n”); }
  }

  scanf(“%d”, &breath);

 return 0;
}

회사 숙제로 구현한 Merge Sort!!
Recursive로 아주 부드럽게 동작하는 것을 알 수 있다.