c++ - Merge sort not working properly -

within merge sort method have merge function believe working correctly tested elsewhere. when try merge sort whole numbers not sort properly. edit: added merge

code:

void mergesort( int a[], int p, int q ) // pre: p >= 0; q >= 0; a[p..q] initialized // post: a[p..q] sorted in ascending order {     int i;                                     //  counter used initialize l , r     int j;     int m;                                     // midpoint of     int l[100];                                // lower half of     int r[100];                                // upper half of      if ( p < q )                               // if list contains more 1 value     {         m = ( p + q ) / 2;                     // find midpoint          j = 0;          ( = p; <= m; i++ )             // initialize lower half of array         {             l[j] = a[i];             j++;         }          j = 0;          ( = m + 1; <= q; i++ )         // initialize upper half of array         {             r[j] = a[i];             j++;         }           mergesort( a, p, m );                  // call mergesort lower half of array          mergesort( a, m + 1, q );              // call mergesort upper half of array          merge( l, r, m - p + 1, q - m, );    // merge both sides     }    }  void merge( int l[], int r[], int l_size, int r_size, int a[] ) // pre: l_size > 0; r_size > 0; l[0..l_size-1] in ascending order; //      r[0..r_size-1] in ascending order; allocated l_size + r_size // post: a[0..l_size+r_size-1] contains elements of l[0..l_size-1] ,                    r[0..r_size-1] {     int i;                                 // counter used fill @ end of algorithm     int l_ctr;                             // counter used traverse l     int r_ctr;                             // counter used traverse r     int a_ctr;                             // counter used traverse      l_ctr = 0;     r_ctr = 0;                             // set counters equal 0     a_ctr = 0;      while ( l_ctr < l_size && r_ctr < r_size ) // loop runs until reaching end of list     {         if ( l[l_ctr] < r[r_ctr] )            // if lowest remain ing value in l         {                                     // lower lowest remaining value in r;             a[a_ctr] = l[l_ctr];              // set next index of l[l_ctr]             l_ctr++;                          // increment l_ctr 1         }         else                                       // else same r_ctr         {             a[a_ctr] = r[r_ctr];             r_ctr++;         }         a_ctr++;                                   // increment a_ctr 1     }      if ( l_ctr < l_size )                          // if of l has not been seen yet     {         ( = l_ctr; < l_size; i++ )         // loop sets remaining values in l         {                                          // last values of             a[a_ctr] = l[i];             a_ctr++;         }     }     else                                           // else same r     {         ( = r_ctr; < r_size; i++ )         {             a[a_ctr] = r[i];             a_ctr++;         }     } } 

your merge step always uses a[0] destination merge 2 ranges. want ranges described indices [p..m] , [m+1..q] go a[p..q]. there @ least 2 simple fixes.

• pass a+p last parameter merge (or use &a[p], they're same).
• pass p additional parameter merge , use initialize a_ctr.

pick either 1 , test it.

edit:

i tested code locally , see recursive calls mergesort should moved below line compute m. following lines copy temp arrays belong merge process , should after recursive calls.

working example @ ideone.com