anonymous mergeSort
No License C++
2019年06月22日
Copy Clone
#include<iostream>
#include<vector>
using namespace std;
const int SENTINEL=(1<<29);

void merge(vector<int>&A,int left,int mid,int right){
  int lm=mid-left,mr=right-mid;
  vector<int> L(lm+1),R(mr+1);
  copy(A.begin()+left,A.begin()+left+lm,L.begin());
  copy(A.begin()+mid,A.begin()+mid+mr,R.begin());
  L[lm]=R[mr]=SENTINEL;
  int Ldx=0,Rdx=0;
  for(int i=left;i<right;++i){
    if(L[Ldx]>R[Rdx])A[i]=R[Rdx++];
    else A[i]=L[Ldx++];
  }

}

void mergeSort(vector<int>&A,int left,int right){
  if(left+1<right){
    int mid=(left+right)/2;
    mergeSort(A,left,mid);
    mergeSort(A,mid,right);
    merge(A,left,mid,right);
  }
}

int main(){

  int n;
  cin>>n;
  vector<int>A(n);
  for(auto&a:A)cin>>a;

  mergeSort(A,0,n);

  for(auto a:A)cout<<a<<" ";
  cout<<endl;

  return 0;
}
#include<iostream>
#include<vector>
using namespace std;
const int SENTINEL=(1<<29);

void merge(vector<int>&A,int left,int mid,int right){
  int lm=mid-left,mr=right-mid;
  vector<int> L(lm+1),R(mr+1);
  copy(A.begin()+left,A.begin()+left+lm,L.begin());
  copy(A.begin()+mid,A.begin()+mid+mr,R.begin());
  L[lm]=R[mr]=SENTINEL;
  int Ldx=0,Rdx=0;
  for(int i=left;i<right;++i){
    if(L[Ldx]>R[Rdx])A[i]=R[Rdx++];
    else A[i]=L[Ldx++];
  }

}

void mergeSort(vector<int>&A,int left,int right){
  if(left+1<right){
    int mid=(left+right)/2;
    mergeSort(A,left,mid);
    mergeSort(A,mid,right);
    merge(A,left,mid,right);
  }
}

int main(){

  int n;
  cin>>n;
  vector<int>A(n);
  for(auto&a:A)cin>>a;

  mergeSort(A,0,n);

  for(auto a:A)cout<<a<<" ";
  cout<<endl;

  return 0;
}
No one still commented. Please first comment.