Проблема с Merge Sort - реализация в C++

Question

Я следую Merge Сортировать алгоритм, предложенный в 2.3.1 из Введение в алгоритмы по Cormen. Однако я не получаю правильный вывод. Я уверен, что здесь есть какая-то глупая ошибка, но я не мог понять это в течение некоторого времени. Любая помощь могла бы быть полезна.

e.g: Для ввода: 5,4,3,2,1, мой выход 3 1 2 4 5 вместо 1 2 3 4 5.

Предположим, что код будет проверен на очень маленькие цифры, а замена значения дозорного значения ∞ (в алгоритме) на 999 не влияет на программу.

Вот код и соответствующие этапы алгоритма в комментариях. Выполнение этого - here.

#include <iostream> 
using namespace std; 

void merge(int* A, int p, int q, int r) {  // MERGE(A,p,q,r) 
    int n1 = q-p+1;        // 1. n1 = q-p+1 
    int n2 = r-q;        // 2. n2 = r-q 

    int i,j,k; 
    int *L=new int[n1+1], *R = new int[n2+1]; // 3. let L[1...n1+1] and R[1..n2+1] be new arrays 

    for(i=0; i<n1; i++)       // 4. for i = 1 to n1 
     L[i]=A[p+i];       // 5. L[i] = A[p+i-1] 
     //the modification in above line is deliberately done to avoid IndexOutOfBounds when p=i=0 and is not because I forgot to subtract 1    
    for(j=0; j<n2;j++)       // 6. for j = 1 to n2 
     R[j]=A[q+j];       // 7. R[j] = A[q+j] 

    L[n1]=999; //sentinel      // 8. L[n1+1]= ∞ 
    R[n2]=999; //sentinel      // 9. R[n2+1]= ∞ 
    i=0;          // 10. i = 1 
    j=0;          // 11. j = 1 
    for(k=p; k<r; k++) {      // 12. for k = p to r 
     if(L[i]<=R[j])       // 13. if(L[i]<=R[j]) 
      A[k]=L[i++];      // 14.   A[k] = L[i] 
               // 15.   i = i+1 
     else         // 16. else A[k] = R[j] 
      A[k]=R[j++];      // 17.   j = j+1     
    } 

    delete(L); 
    delete(R); 
} 

void mergeSort(int* a, int p, int r) {  // MERGE-SORT (A,p,r) 
    if(p<r) {         // 1. if p<r 
     int q=(p+r)/2;      // 2. q = (p+r)/2 
     mergeSort(a,p,q);      // 3. MERGE-SORT(A,p,q) 
     mergeSort(a,q+1,r);     // 4. MERGE-SORT(A,q+1,r) 
     merge(a,p,q,r);      // 5. MERGE(A,p,q,r) 
    } 
} 

int main() { 
    int arr[]={5,4,3,2,1}; 
    mergeSort(arr,0,5); 

    for(int i=0; i<5; i++) 
     cout << arr[i]<<" "; 
} 

Answer 1

Ваши рекурсивные вызовы в mergeSort предположить, что p и r являются индексы первого и последнего элемента подмассива для сортировки:

void mergeSort(int* a, int p, int r) { 
    if(p<r) { 
     int q=(p+r)/2; 
     mergeSort(a,p,q); 
     mergeSort(a,q+1,r); 
     merge(a,p,q,r); 
    } 
} 

Если да, то ваш звонок в main неправилен:

int arr[]={5,4,3,2,1}; 
mergeSort(arr,0,5); 

должен быть

int arr[]={5,4,3,2,1}; 
mergeSort(arr,0,4); 

Далее, копируя вторую половину не так:

R[j]=A[q+j]; 

должно быть:

R[j]=A[q+1+j]; 

Обратите внимание, что p является индекс первого элемента в левой половине, в то время как q является индексом из последний элемент левой половины - поэтому первый элемент правой половины имеет индекс q+1, и это должно быть принято в качестве базы для +j.

Наконец,

for(k=p; k<r; k++) 

следует читать

for(k=p; k<=r; k++) 

- r является индекс последнего элемента в правой части, так что вам нужно заполнить [r] позицию присоединяемого подмассива.

EDIT
См my answer к Sorting of an array using merge sort.

Answer 2

L[i]=A[p+i];       // 5. L[i] = A[p+i-1] 

Я думаю, что это ваша проблема, вы не следовать алгоритму здесь, фиксируя его немного (не используя -1, потому что, начиная с 0), а в следующем цикле, вы не» t +1, когда вы также не начинаете с того же числа в алгоритме?

R[j]=A[q+j];       // 7. R[j] = A[q+j] 

В предыдущем цикле вы вручную исправляете значение, начинающееся с 0, а не 1, но здесь вы этого не делаете.