SPFort - 1 year ago 34

C++ Question

I am trying to write a merge sort algorithm using template functions in c++. The output is close but not correct. I specifically believe that the problem is in the merge function rather than the merge sort function. Any help would be much appreciated. Here is my code:

`template <class T1>`

void mergeSort(T1 array[], int lower, int upper)

{

if (lower < upper)

{

int middle = (lower + upper) / 2;

mergeSort(array, lower, middle);

mergeSort(array, middle + 1, upper);

merge(array, lower, middle, upper);

}

}

template <class T1>

void merge(T1 array1[], int lower, int middle, int upper)

{

int i = 0,

j = 0,

k = 0;

int size1 = middle - lower + 1;

int size2 = upper - middle;

T1* temp1 = new T1[size1];

T1* temp2 = new T1[size2];

for (int i = 0; i < size1; i++)

{

temp1[i] = array1[lower + i];

}

for (int j = 0; j < size2; j++)

{

temp2[j] = array1[middle + 1 + j];

}

while (i < size1 && j < size2)

{

if (temp1[i] < temp2[j])

{

array1[k] = temp1[i];

i++;

}

else

{

array1[k] = temp2[j];

j++;

}

k++;

}

if (i == size1)

{

while (j < size2)

{

array1[k] = temp2[j];

k++;

j++;

}

}

else

{

while (i < size1)

{

array1[k] = temp1[i];

k++;

i++;

}

}

}

int main(){

int a[] = { 7, 6, 4, 8, 1, 2, 3 };

mergeSort(a, 0, 6);

}

Output:

`1 1 2 2 3 3 8`

Answer Source

In your `merge`

function you shouldn't initialize `k`

to 0 because it will write the result of merge in the wrong place. Instead you should initialize `k`

to `lower`

. Because that is the start index of the part you are actually sorting.