ssaber ssaber - 1 month ago 15
C++ Question

C++ MergeSort implementation: duplicate elements replacing others in the result

I am trying to write a mergeSort function, it seems to be working well most of the time. But, in some testcases, the final result contains duplicates that have replaced other elements. For example in this test case: {100, 56, 7, 7, 8, 2, 7, 6, 10, 11, 15, 88, 4, 6, 3} the output is: {2, 3, 4, 6, 6, 7, 7, 7, 8, 10, 11, 15, 15, 56, 100}. As you can see in the last 4 elements, the number 15 is duplicated and the number 88 is missing. I am not sure why this is happening.
I've checked this link: Merge Sort Not Properly Sorting (C++)
but it's not the same problem.

this is how I call the merge:

void mergeSort(int* a, int start, int end) //we want end here to be the ending index not the size
{
int mid;
if(start < end) //if there are at least two elements
{
mid = (start + end)/2; //calculate middle location

mergeSort(a, start, mid); //left half of the array
mergeSort(a, mid + 1, end);//right half of the array
merge(a, start, mid, end);//merge two halves together
}

}


and then this is the other function:

void merge(int* a, int start, int mid, int end)
{
int* b = new int[end+1]; //create another array b of size end+1 (since end is the ending index not the size)

for (int k=start; k<=end; k++)
b[k] = a[k]; //copy elements from array a to array b

int i, j, z;
i = start;
j = mid + 1;
z = start;
while ((i <= mid) && (j<=end))
{
if (b[i] <= b[j])
{
a[z]=b[i];
i++;
}
else
{
a[z]=b[j];
j++;
}
z++; //increment the index in array (a)
}

if (i<=mid) //if there are still unmerged elements in the left array
{
for (int k = i; k<=mid; k++)
a[z++] = b[k];
}
else if(j<=end) //if there are still unmerged elements in the right array
{
for (int k=j; j<=end; j++)
a[z++]=b[k];
}

}


Thanks in advance!!

Answer

You have typo in last loop:

for (int k=j; j<=end; j++)

should be

for (int k=j; k<=end; k++)

Or you can replace

if (i<=mid) //if there are still unmerged elements in the left array
{
    for (int k = i; k<=mid; k++)
        a[z++] = b[k];
}
else if(j<=end) //if there are still unmerged elements in the right array
{
    for (int k=j; j<=end; j++)
        a[z++]=b[k];
}

by

while (i <= mid) {
    a[z++] = b[i++];
}
while (j <= end) {
    a[z++] = b[j++];
}