пятница, 4 января 2013 г.

Реализация сортировки слиянием (Merge Sort) на С++



const int INFINITY=1E10;

template < typename Type>
void Merge(Type mas[], int left, int m, int right) {
 int n1=m-left+1;
 int n2=right-m;
 vector < Type> L(n1+1);
 vector < Type> R(n2+1);
 for (int i=0; i< n1; ++i){
  L[i]=mas[left+i];
 }
 for (int i=0; i< n2; ++i){
  R[i]=mas[m+i+1];
 }

 L[n1]=INFINITY;
 R[n2]=INFINITY;

 for (int k=left,i=0,j=0;k< =right;++k) {
  if (L[i]< =R[j]){
   mas[k]=L[i]; 
   i++;
  }
  else {
   mas[k]=R[j];
   j++;
  }
 }
}

template < typename Type>
void Merge_Sort (Type mas[], int l, int r) {
 if (l>=r) return;
 int middle=(l+r)/2;
 Merge_Sort (mas,l,middle);
 Merge_Sort(mas,middle+1,r);
 Merge(mas,l,middle,r);
}

0 коммент.:

Отправить комментарий