병합정렬(합병정렬) mergesort 여러 소스 코드들 참조.

재귀의 형태로 분할시키고 merge와 sort를 나누는 방식이 보통이다.


[code cpp:nocontrols]
void MergeSort(int iArray[], int iTemp[], int iStart, int iEnd)
{
    if (iStart < iEnd) {
        int iMid = (iStart + iEnd)/2;
        MergeSort(iArray, iTemp, iStart, iMid);
        MergeSort(iArray, iTemp, iMid + 1, iEnd);
        Merge(iArray, iTemp, iStart, iMid, iEnd);
    }
}
void Merge(int iArray[], int iTemp[], int iLow, int iMid, int iHigh)
{
    int h = iLow, i = iLow, j = iMid+1, k;
    while ((h <= iMid) && (j <= iHigh)) {
        if (iArray[h] <= iArray[j]) { iTemp[i] = iArray[h]; h++; }
        else { iTemp[i] = iArray[j]; j++; } i++;
    }
    if (h > iMid) {
        for (k=j; k<=iHigh; k++) {
            iTemp[i] = iArray[k]; i++;
        }
    }
    else {
        for (k=h; k<=iMid; k++) {
            iTemp[i] = iArray[k]; i++;
        }
    }
    for (k=iLow; k<=iHigh; k++) iArray[k] = iTemp[k];
}
[/code]

// ------------------ 아래는  다른 버전 -----------------------------//

void mergeSort(int numbers[], int temp[], int array_size)
{
  m_sort(numbers, temp, 0, array_size - 1);
}


void m_sort(int numbers[], int temp[], int left, int right)
{
  int mid;

  if (right > left)
  {
    mid = (right + left) / 2;
    m_sort(numbers, temp, left, mid);
    m_sort(numbers, temp, mid+1, right);

    merge(numbers, temp, left, mid+1, right);
  }
}

void merge(int numbers[], int temp[], int left, int mid, int right)
{
  int i, left_end, num_elements, tmp_pos;

  left_end = mid - 1;
  tmp_pos = left;
  num_elements = right - left + 1;

  while ((left <= left_end) && (mid <= right))
  {
    if (numbers[left] <= numbers[mid])
    {
      temp[tmp_pos] = numbers[left];
      tmp_pos = tmp_pos + 1;
      left = left +1;
    }
    else
    {
      temp[tmp_pos] = numbers[mid];
      tmp_pos = tmp_pos + 1;
      mid = mid + 1;
    }
  }

  while (left <= left_end)
  {
    temp[tmp_pos] = numbers[left];
    left = left + 1;
    tmp_pos = tmp_pos + 1;
  }
  while (mid <= right)
  {
    temp[tmp_pos] = numbers[mid];
    mid = mid + 1;
    tmp_pos = tmp_pos + 1;
  }

  for (i=0; i <= num_elements; i++)
  {
    numbers[right] = temp[right];
    right = right - 1;
  }
}

//------------------- 이건 도식화 ---------------------