本文共 1560 字，大约阅读时间需要 5 分钟。

Write a program of a Merge Sort algorithm implemented by the following pseudocode. You should also report the number of comparisons in the Merge function.

Merge(A, left, mid, right)  n1 = mid - left;  n2 = right - mid;  create array L[0...n1], R[0...n2]  for i = 0 to n1-1    do L[i] = A[left + i]  for i = 0 to n2-1    do R[i] = A[mid + i]  L[n1] = SENTINEL  R[n2] = SENTINEL  i = 0;  j = 0;  for k = left to right-1    if L[i] <= R[j]      then A[k] = L[i]           i = i + 1      else A[k] = R[j]           j = j + 1Merge-Sort(A, left, right){  if left+1 < right    then mid = (left + right)/2;         call Merge-Sort(A, left, mid)         call Merge-Sort(A, mid, right)         call Merge(A, left, mid, right

Input

In the first line n is given. In the second line, n integers are given.

Output

In the first line, print the sequence S. Two consequtive elements should be separated by a space character.

In the second line, print the number of comparisons.

Constraints

• n ≤ 500000
• 0 ≤ an element in S ≤ 109

Sample Input 1

108 5 9 2 6 3 7 1 10 4

Sample Output 1

1 2 3 4 5 6 7 8 9 1034

 代码如下：

#include 
   
    #include 
    
     #include 
     
      #include 
      
       using namespace std;const int maxn=500005;const int INF=0x3f3f3f3f;int n;int a[maxn];int cnt=0;void Sort (int left,int mid,int right){    int L[(maxn>>1)+10],R[(maxn>>1)+10];    int numl=mid-left;    int numr=right-mid;    for (int i=0;i
       
        >1;        Merge (left,mid);        Merge (mid,right);        Sort (left,mid,right);    }}int main(){    scanf("%d",&n);    for (int i=0;i
       
      
     
    
   

转载地址：http://hpaen.baihongyu.com/