Почему код сортировки ниже слияния не работает?

Question

Что следует изменить в приведенном ниже коде? Он показывает следующей ошибку

ERROR: ld.so: object '/home/bot/funcs.so' from LD_PRELOAD cannot be preloaded (cannot open shared object file): ignored.

Error in `/home/bot/dcb7b4b8f54571a4467c2113b7856878': free(): invalid next size (fast): 0x0000000000c350b0

 #include <iostream> 

     using namespace std; 

     int merge(int *left,int nl,int *right,int nr,int *a) 
     { 

     int i=0,j=0,k=0; 
     while(i<nl && j<nr) 
     { 
      if(left[i]<right[j]) 
      { 
      a[k]=left[i]; 
      i++; 
      } 
      else 
      { 
      a[k]=right[j]; 
      j++; 
      } 
      k++; 
      } 
     while(i<nl) 
     { 
     a[k]=left[i]; 
      i++; 
     } 
     while(j<nr) 
     { 
     a[k]=right[j]; 
     j++; 
     } 
} 
int mergesort(int *a,int n) 
{ 

     if(n<2) return 0; 
     int mid=n/2; 
     int *left=new int[mid]; 
     int *right=new int[n-mid]; 

    for(int i=0;i<=mid-1;i++) 
    { 
     left[i]=a[i]; 
    } 
    for(int i=mid;i<=n-1;i++) 
    { 
     right[i]=a[i]; 
    } 
     mergesort(left,mid); 
     mergesort(right,n-mid); 
     merge(left,mid,right,n-mid,a); 
    delete[]left; 
    delete[]right; 
    } 

    int main() { 
     //code 
     int a[]={10,7,8,9,4,2,3,6,5,1}; 
     int n=sizeof(a)/sizeof(a[0]); 
     mergesort(a,n); 
     for(int i=0;i<10;i++) 
     { 
     cout<<a[i]<<"\t"; 
     } 
     return 0; 
     } 

Answer 1

Исправления, отмеченные в комментариях, похоже, работают сейчас. Однократное распределение временного массива как в основной, так и в вспомогательной функции будет быстрее. Используя взаимно рекурсивные функции (один объединяет AtoA, другой объединяет AtoTemp, они называют друг друга), исключает необходимость копирования данных. Я могу отправить пример позже, если захочет. Сорт слияния снизу будет немного быстрее.

#include <iostream> 

using namespace std; 

// fix return type to void 
void merge(int *left,int nl,int *right,int nr,int *a) 
{ 
    int i=0,j=0,k=0; 
    while(i<nl && j<nr) 
    { 
     if(left[i]<right[j]) 
     { 
      a[k]=left[i]; 
      i++; 
     } 
     else 
     { 
      a[k]=right[j]; 
      j++; 
     } 
     k++; 
    } 
    while(i<nl) 
    { 
     a[k]=left[i]; 
     i++; 
     k++;     // fix 
    } 
    while(j<nr) 
    { 
     a[k]=right[j]; 
     j++; 
     k++;     // fix 
    } 
} 

// fix return type to void 
void mergesort(int *a,int n) 
{ 
    if(n<2) return;    // fix: change return type to void 
    int mid=n/2; 
    int *left=new int[mid]; 
    int *right=new int[n-mid]; 

    for(int i=0;i<=mid-1;i++) 
    { 
     left[i]=a[i]; 
    } 
    for(int i=mid;i<=n-1;i++) 
    { 
     right[i-mid]=a[i];  // fix 
    } 
    mergesort(left,mid); 
    mergesort(right,n-mid); 
    merge(left,mid,right,n-mid,a); 
    delete[]left; 
    delete[]right; 
} 

int main() { 
    //code 
    int a[]={10,7,8,9,4,2,3,6,5,1}; 
    int n=sizeof(a)/sizeof(a[0]); 
    mergesort(a,n); 
    for(int i=0;i<10;i++) 
    { 
     cout<<a[i]<<"\t"; 
    } 
    cout << endl;    // added this not needed 
    return 0; 
} 

Cleanup, изменяющий не использовать вкладки:

#include <iostream> 
#include <iomanip>    // for std::setw() 

using namespace std; 

void merge(int *left,int nl,int *right,int nr,int *a) 
{ 
    int i=0,j=0,k=0; 
    while(i<nl && j<nr) 
    { 
     if(left[i]<right[j]) 
      a[k++]=left[i++]; 
     else 
      a[k++]=right[j++]; 
    } 
    while(i<nl) 
     a[k++]=left[i++]; 
    while(j<nr) 
     a[k++]=right[j++]; 
} 

void mergesort(int *a,int n) 
{ 
    if(n<2) 
     return; 
    int mid=n/2; 
    int *left=new int[mid]; 
    int *right=new int[n-mid]; 

    for(int i=0;i<=mid-1;i++) 
     left[i]=a[i]; 
    for(int i=mid;i<=n-1;i++) 
     right[i-mid]=a[i]; 
    mergesort(left,mid); 
    mergesort(right,n-mid); 
    merge(left,mid,right,n-mid,a); 
    delete[]left; 
    delete[]right; 
} 

int main() { 
    int a[]={10,7,8,9,4,2,3,6,5,1}; 
    int n=sizeof(a)/sizeof(a[0]); 
    mergesort(a,n); 
    for(int i=0;i<10;i++) 
     cout<<setw(2)<<a[i]<<" "; // 2 digit field output 
    cout << endl; 
    return 0; 
} 

Answer 2

Вы должны использовать std::vector вместо сырого указателя:

typedef std::vector<int> ivector; 

void merge(const ivector &l, const ivector &r, ivector &to) 
{ 
    ivector_const::iterator il = l.begin(); 
    ivector_const::iterator ir = r.begin(); 
    ivector::iterator ito = to.begin(); 

    while(true) { 
     if(il == l.end()) { 
       if(ir == r.end()) 
        return; 
       *ito++ = *ir++; 
     } else { 
       if(ir == r.end() || *il < *ir) 
        *ito++ = *il++; 
       else 
        *ito++ = *ir++; 
     } 
    } 
} 

void mergesort(ivector &v) 
{ 
     if(v.size()<2) return; 
     ivector::iterator imid = v.begin() + v.size()/2; 
     ivector left(v.begin(), imid); 
     ivector right(imid, v.end()); 

     mergesort(left); 
     mergesort(right); 
     merge(left, right, v); 
} 

int main() { 
    //code 
    ivector a ={10,7,8,9,4,2,3,6,5,1}; 
    mergesort(a); 
    for(size_t i=0;i<a.size();i++) 
    { 
     cout<<a[i]<<"\t"; 
    } 
    return 0; 
} 

Примечания: Я не проверял ваш алгоритм просто переписал его с std::vector вместо сырого указателя. Вы можете заметить, насколько проще ваша функция стать, когда вы используете правильный тип данных.