# Merge Sort - Invalid Output ??

• 09-25-2005
gqchynaboy
Merge Sort - Invalid Output ??
Code:

```#include <iostream> using namespace std; void mergeSort(int a[], int low, int high); void merge (int a[], int low1, int high1, int low2, int high2); int main()   {   int sort[10]={6, 5, 8, 2, 12, 21, 11, 15, 25, 32};   mergeSort(sort,0,9);   for(int i =0; i<10; i++)       {       cout << sort[i] << endl;       }   return 0;   } void mergeSort(int a[], int low, int high)   {   if (low >=high) return;   int mid = (low+high)/2;   mergeSort(a, low, mid);   mergeSort(a, mid+1, high);   merge(a, low, mid, mid+1, high);   } void merge(int a[], int low1, int high1, int low2, int high2)   {   int t, i1, i2;   int *temp;   i1 = low1;   i2 = low2;   t = 0;   while (i1 <= high1 && i2 <= high2)     {     if (a[i1] < a[i2])       temp[t++] = a[i1++] ;     else       temp[t++] = a[i2++] ;     }   while (i1 <= high1)     temp[t++] = a[i1++] ;   while (i2 <= high2)     temp[t++] = a[i2++] ;   for (t = low1; t <= high2; t++)       {       a[t] = temp[t - low1] ;       }   }```
Output I get is

11
11
11
11
11
11
15
21
25
32

• 09-25-2005
Salem
> int *temp;
Well this isn't pointing anywhere at the moment.

Even if it did, it would still need to be copied back to the original array.

I thought the merge was supposed to take place in the original array?
• 09-25-2005
gqchynaboy
Quote:

Originally Posted by Salem
> int *temp;
Well this isn't pointing anywhere at the moment.

Even if it did, it would still need to be copied back to the original array.

I thought the merge was supposed to take place in the original array?

thanks I fixed it now it works

int temp[10];
• 09-25-2005
Prelude
>I thought the merge was supposed to take place in the original array?
Not if you want it to be reasonably efficient. An in-place merge is a pain to get right, and it's much slower than using O(N) extra space. That's why merge sort isn't such a good option for arrays, but kicks butt for linked lists. So for arrays you merge to the auxiliary array, then copy back to the original array and wonder why you didn't use quicksort. ;)