SPFort SPFort - 2 months ago 6
C++ Question

incorrect output of merge sort

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

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.

Comments