mergesort - Issue with Merge Sort - Implementation in C++ -

i following merge sort algorithm suggested in 2.3.1 of introduction algorithms cormen. however, not getting correct output. sure there's silly mistake in here, haven't been able figure out time now. appreciated.

e.g: input : 5,4,3,2,1, output 3 1 2 4 5 instead of 1 2 3 4 5.

assume code tested small numbers, , replacing sentinel value ∞ (in algorithm) 999 not affect program.

here code , corresponding steps of algorithm in comments. execution of 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] , r[1..n2+1] new arrays      for(i=0; i<n1; i++)                         //   4. = 1 n1         l[i]=a[p+i];                            //   5.    l[i] = a[p+i-1]        //the modification in above line deliberately done avoid indexoutofbounds when p=i=0 , not because forgot subtract 1                    for(j=0; j<n2;j++)                          //   6. j = 1 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. = 1     j=0;                                        //  11. j = 1     for(k=p; k<r; k++) {                        //  12. k = p r          if(l[i]<=r[j])                          //  13.    if(l[i]<=r[j])             a[k]=l[i++];                        //  14.         a[k] = l[i]                                                 //  15.         = 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]<<" "; } 

your recursive calls mergesort suggest p , r indices of first , last item of subarray sorted:

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);     } } 

if so, call in main incorrect:

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

should be

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

next, copying second half wrong:

r[j]=a[q+j]; 

should be:

r[j]=a[q+1+j]; 

note p index of first item in left half, while q index of last item of left half – first item of right half has index q+1, , should taken base +j.

finally,

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

should read

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

– r index of last item in right part, need fill [r] position of merged subarray.

edit
see my answer sorting of array using merge sort.