c++ - Recursive Merge Sort Function Giving Bad Output -

i trying figure out why merge sort function not working. believe problem within merge() part of it. here code:

int mergesort(int *data, int left, int right) {     //divide     if (left < right) {         int q = floor((left + right) / 2);         //conquer         mergesort(data, left, q);         mergesort(data, q + 1, right);         //combine         merge(data, left, q, right);     }      //print results testing purposes     (int = 0; < n; i++) {         cout << data[i] << "\n";     }      return 0; } 

and here merge() part of it. believe problem within part.

int merge(int *data, int left, int q, int right) {     int *temp = data;     int = left, j = q + 1, z = left;     int t1 = 0, t2 = 0;     while (i <= q && j <= right) { //while both variables have not reached end of sub arrays         if (temp[i] <= temp[j]) {             data[z] = temp[i];             i++;         }         else {             data[z] = temp[j];             j++;         }         z++;     }      //if subarrays both sorted , in order, combine them     if (i < q) {         t1 = z, t2 = i;         (t1; t1 < right;) {             data[t1] = temp[t2];             t1++;             t2++;         }     }      else if (j < right) {         int t1 = z; int t2 = j;         (t1; t1 <= right;) {             data[t1] = temp[t2];             t1++;             t2++;         }     }  

i think problem coming declaring int *temp = data; @ beginning of merge(). thought i'm getting kind of memory address conflict between these 2 arrays, i'm not sure.

i have tried arranging data in different order, , have found when data needs moved index n index n-i, each index between these 2 indices replaced value of n. example:

the passing in array {4, 13, 8, 12, 9 } return {4, 8, 8, 9, 9}

my other thought , j variables not incrementing correctly. have been on code repeatedly , can't seem find solution.

this (first line of merge function)

int *temp = data; 

does not copy array; creates pointer pointing same memory. causes code overwrite data.

you need this:

int * temp = new int [right - left + 1]; memcpy (temp, data + left, (right - left + 1) * sizeof(int)); 

and don't forget delete[] memory temp @ end of function:

delete[] temp; 

note you'll need change use of z; should start 0, not left.

(the following optional performance improvements; can ignore them.) allocating , freeing memory in each merge function bad idea. specially since know how total memory need merging: array of n integers.

for reason, it's better idea pass in array of same size along data mergesort, can used scratch memory (i.e. temp memory) merging. or if clever, can ping-pong between actual , scratch memory minimize copying.