2751 : 수 정렬하기 2 (TopDownMerge) [C++]

#include <iostream>

using namespace std;

void TopDownMergeSort(int A[], int B[], int n);
void TopDownSplitMerge(int B[], int iBegin, int iEnd, int A[]);
void TopDownMerge(int A[], int iBegin, int iMiddle, int iEnd, int B[]);
void CopyArray(int A[], int iBegin, int iEnd, int B[]);

int main()
{
 cin.tie(NULL);

 int N;
 cin >> N;

 int* X = new int[N];

 for (int i = 0; i < N; i++)
  cin >> X[i];

 int* Y = new int[N];

 TopDownMergeSort(X, Y, N);

 for (int i = 0; i < N; i++)
  cout << X[i] << "\n";
}


// Array A[] has the items to sort; array B[] is a work array.
void TopDownMergeSort(int A[], int B[], int n)
{
 CopyArray(A, 0, n, B);           // duplicate array A[] into B[]
 TopDownSplitMerge(B, 0, n, A);   // sort data from B[] into A[]
}

// Sort the given run of array A[] using array B[] as a source.
// iBegin is inclusive; iEnd is exclusive (A[iEnd] is not in the set).
void TopDownSplitMerge(int B[], int iBegin, int iEnd, int A[])
{
 if (iEnd - iBegin < 2)                       // if run size == 1
  return;                                 //   consider it sorted
            // split the run longer than 1 item into halves
 int iMiddle = (iEnd + iBegin) / 2;              // iMiddle = mid point
            // recursively sort both runs from array A[] into B[]
 TopDownSplitMerge(A, iBegin, iMiddle, B);  // sort the left  run
 TopDownSplitMerge(A, iMiddle, iEnd, B);  // sort the right run
            // merge the resulting runs from array B[] into A[]
 TopDownMerge(A, iBegin, iMiddle, iEnd, B);
}

//  Left source half is A[ iBegin:iMiddle-1].
// Right source half is A[iMiddle:iEnd-1   ].
// Result is            B[ iBegin:iEnd-1   ].
void TopDownMerge(int A[], int iBegin, int iMiddle, int iEnd, int B[])
{
 int i = iBegin, j = iMiddle;

 // While there are elements in the left or right runs...
 for (int k = iBegin; k < iEnd; k++) {
  // If left run head exists and is <= existing right run head.
  if (i < iMiddle && (j >= iEnd || A[i] <= A[j])) {
   B[k] = A[i];
   i = i + 1;
  }
  else {
   B[k] = A[j];
   j = j + 1;
  }
 }
}

void CopyArray(int A[], int iBegin, int iEnd, int B[])
{
 for (int k = iBegin; k < iEnd; k++)
  B[k] = A[k];
}

MergeSort는 https://ko.wikipedia.org/wiki/%ED%95%A9%EB%B3%91_%EC%A0%95%EB%A0%AC 에서 참조했다.