数据结构练习：自写的想法写归并排序 2020.11.20

#include <iostream>
#include<vector>
using namespace std;
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
void merge_short(vector<int> &q,int l,int r);
void merge_short(vector<int> &q,int l,int r) 
{
  int mid=(l+r)/2;
  if(l==r)
    return;
  int left=l,right=r,i,r2=mid+1; 
  merge_short(q,l,mid);
  merge_short(q,mid+1,r);
  static vector<int> w;
  w.clear();
  //将较小的数据存放在临时数组中 
  while(l<=mid&&r2<=r)
  {
    if(q[l]<=q[r2])
    {
      w.push_back(q[l++]);
    }
    else
    {
      w.push_back(q[r2++]);
    }
  }
  while(l<=mid)w.push_back(q[l++]);//将l到r的剩余数据存储到w中 
  while(r2<=r)w.push_back(q[r2++]);
  for(i=left;i<=mid;i++)//将w中排好序的数据填充到原数组中 
  {
    q[i]=w[i-left];
  }
  for(int j=mid+1;j<=right;j++,i++)
  {
    q[j]=w[i-left];
  }
  return;
}
int main(int argc, char** argv) {
  vector<int> a;
  int i=0,n;
  cin>>n;
  for(i=0;i<n;i++)
  {
    int b;
    cin>>b;
    a.push_back(b);
  }
  merge_short(a,0,a.size()-1);
  for(i=0;i<a.size();i++)
  {
    printf("%d  ",a[i]);
   } 
  return 0;
}