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

#include "stdafx.h"
#include"iomanip.h"
#include "iostream.h"
 
#define MAXSIZE 100
//合并两个有序的子数组
void merge(int a[],int p,int q,int r,int m)
{
 int *bp = new int[m]; //分配缓冲区，存放被排序的元素
    int i,j,k;
        i = p;
        j = q+1;
         k = 0;
   while(i<=q && j<=r) //逐一判断两子数组的元素，按两种情况，把小的元素复制到缓冲区
   {
           if(a[i]<=a[j])
     {
             bp[k++] = a[i++];
     }
     else
     {
             bp[k++]=a[j++];
     }
   }
   if (i==q+1)  //按两种情况，处理其余元素
   {
             for (; j<=r ; j++)
     bp[k++] = a[j ];    //把a【j】~a【r】复制到缓冲区
   }
   else
   {
             for (; i<=q ; i++)
     bp[k++] = a[i  ];  //把a【i】~a【q】复制到缓冲区
   }
   k = 0;
   for(i = p; i<=r;i++)
    a[i ] = bp[k++];     //最后，，把数组bp的内容复制到a【p】~a【r】中
   delete bp;

}

//合并排序算法

void merge_sort(int a[],int n)
{
  int i,s,t = 1; //i:为开始合并时第一个序列的起始位置，s:为合并前序列的大小，t:为合并后序列的大小
  while (t < n)
  {
   s = t;
   t = 2 * s;
   i = 0;
   while (i+t<n)
   {
          merge(a,i,i+s-1,i+t-1,t);
    i = i + t;
   }
   if(i+s<n)
    merge(a,i,i+s-1,n-1,n-i);
  }
}
//输入n个元素的数组a【】以及个数

int main(int argc, char* argv[])
{
 int a[MAXSIZE],n,i;
   cout<<"please input the numbers of array"<<endl;
   cin>>n;
   cout<<"please input every value of element"<<endl;
   for(i = 0;i < n;i++)
   {
    cout<<"please input the"<<setw(5)<<i<<setw(35)<<"element(enter Enter to switch):"<<endl;
    cin>>a[i];
   }
     merge_sort(a,n);

   for(i = 0;i < n;i++)
    cout<<a[i]<<setw(8);

 return 0;
}