//
// Merge Sort
//

void MSort (int A[], int TmpA[], int Left, int Right);

void
MergeSort (int A[], int N)
{
  int TmpA[N];
  MSort (A, TmpA, 0, N-1);
}

void
Merge (int A[], int TmpA[], int LPos, int RPos, int REnd)
{
  int LEnd, N, TmpPos;

  TmpPos = LPos; 
  LEnd = RPos - 1;
  N = REnd - LPos + 1;
  while ((LPos <= LEnd) && (RPos <= REnd))
    {
      if (A[LPos] <= A[RPos])
        TmpA[TmpPos++] = A[LPos++];
      else
        TmpA[TmpPos++] = A[RPos++];
    }
  while (LPos <= LEnd)
    TmpA[TmpPos++] = A[LPos++];
  while (RPos <= REnd)
    TmpA[TmpPos++] = A[RPos++];

  for (int i = 0; i < N; i++, REnd--)
    A[REnd] = TmpA[REnd];
}

void
MSort (int A[], int TmpA[], int Left, int Right)
{
  int Center;
  if (Left < Right)
    {
      Center = (Left + Right) / 2;
      MSort (A, TmpA, Left, Center);
      MSort (A, TmpA, Center+1, Right);
      Merge (A, TmpA, Left, Center+1, Right);
    }
}