mergesort - strange output

[rkk]

Hi,

My mergesort program is below. There is a small piece of logical
error/bug in this code which I can't figure out, as a result the output
array isn't completely sorted. Requesting your help to resolve this
problem. Thanks in advance.

#include <stdlib.h>
#include <string.h>
#include <stdio.h>

typedef int (*CompareFunc)(const void*,const void*);

void MergeSort(void *array[],int left,int right,CompareFunc compare);
void Merge(void *array[],int left,int mid,int right,CompareFunc
compare);
int IntCompare(const void *a,const void *b);
int StrCompare(const void *a,const void *b);

void MergeSort(void *array[],int left,int right,CompareFunc compare)
{
int mid;
if ( left >= right ) return;
mid = (left + right)/2;
MergeSort(array,left,mid,compare);
MergeSort(array,mid + 1,right,compare);
Merge(array,left,mid,right,compare);
}

void Merge(void *array[],int left,int mid,int right,CompareFunc
compare)
{
int numElements = right - left + 1;
void **aux;
int lowerBound = left,upperBound = mid + 1,index = 0;
aux = malloc(numElements * sizeof &array[0]);
if(aux == NULL) {
fprintf(stderr,"Merge: %s\n","malloc failed");
return;
}
while ( lowerBound <= mid && upperBound <= right )
{
if(compare(&array[lowerBound],&array[upperBound]) < 0) {
aux[index++] = array[lowerBound++];
} else {
aux[index++] = array[upperBound++];
}
}
while ( lowerBound <= mid ) aux[index++] = array[lowerBound++];
while ( upperBound <= right) aux[index++] = array[upperBound++];

for(index = left ; index < numElements; index++)
array[index] = aux[index];
free(aux);
}

int IntCompare(const void *a,const void *b)
{
const int *ia = (const int*) a;
const int *ib = (const int*) b;
return ( (*ia *ib) - (*ia < *ib) );
}

int StrCompare(const void *a,const void *b)
{
return strcmp(*(char **) a, *(char **) b);
}

int main()
{
int i;
int iArray[] = {6,3,2,1,4,5,7,9,10,11,13,12,8,14};
int sizeOfArray = sizeof iArray/sizeof iArray[0];
MergeSort((void **)iArray,0,(sizeOfArray-1),IntCompare);
for(i=0; i < sizeOfArray; i++)
printf("%d ", iArray[i] );
printf("\n");
return 0;
}

Here is how I compile:
$ gcc -g -o mergesort mergesort.c

Here is the output:
$ ./mergesort
2 1 3 4 5 6 7 9 10 11 13 12 8 14

Clearly the output isn't completely sorted. Kindly help.

Regards
Kalyan

[Barry Schwarz]

On 30 Sep 2006 07:18:17 -0700, "rkk" <te*******@yahoo.comwrote:

>Hi,

My mergesort program is below. There is a small piece of logical
error/bug in this code which I can't figure out, as a result the output
array isn't completely sorted. Requesting your help to resolve this
problem. Thanks in advance.

#include <stdlib.h>
#include <string.h>
#include <stdio.h>

typedef int (*CompareFunc)(const void*,const void*);

void MergeSort(void *array[],int left,int right,CompareFunc compare);
void Merge(void *array[],int left,int mid,int right,CompareFunc
compare);
int IntCompare(const void *a,const void *b);
int StrCompare(const void *a,const void *b);

void MergeSort(void *array[],int left,int right,CompareFunc compare)
{
int mid;
if ( left >= right ) return;
mid = (left + right)/2;
MergeSort(array,left,mid,compare);
MergeSort(array,mid + 1,right,compare);
Merge(array,left,mid,right,compare);
}

void Merge(void *array[],int left,int mid,int right,CompareFunc
compare)
{
int numElements = right - left + 1;
void **aux;
int lowerBound = left,upperBound = mid + 1,index = 0;
aux = malloc(numElements * sizeof &array[0]);

Conceptually, array is an array of void*. array[0] is the first void*
in the array. &array[0] has type pointer to void* which is expressed
as void**.

aux is a void**. The thing it points to must be a void*. If
sizeof(void*) sizeof(void**) on your system, you are not allocating
enough space.

Eliminate this problem by using sizeof *aux.

> if(aux == NULL) {
fprintf(stderr,"Merge: %s\n","malloc failed");
return;
}
while ( lowerBound <= mid && upperBound <= right )
{
if(compare(&array[lowerBound],&array[upperBound]) < 0) {
aux[index++] = array[lowerBound++];
} else {
aux[index++] = array[upperBound++];
}
}
while ( lowerBound <= mid ) aux[index++] = array[lowerBound++];
while ( upperBound <= right) aux[index++] = array[upperBound++];

for(index = left ; index < numElements; index++)
array[index] = aux[index];
free(aux);
}

int IntCompare(const void *a,const void *b)
{
const int *ia = (const int*) a;
const int *ib = (const int*) b;
return ( (*ia *ib) - (*ia < *ib) );
}

int StrCompare(const void *a,const void *b)
{
return strcmp(*(char **) a, *(char **) b);
}

int main()

int main(void) is preferable.

>{
int i;
int iArray[] = {6,3,2,1,4,5,7,9,10,11,13,12,8,14};
int sizeOfArray = sizeof iArray/sizeof iArray[0];
MergeSort((void **)iArray,0,(sizeOfArray-1),IntCompare);

Here you potentially invoke undefined behavior. You pass the address
of iArray, cast to the correct type, to MergeSort. MergeSort takes
this address and treats the objects (of type int) that it finds there
as having type void*.

Do you know for a fact that an int is properly aligned for a
void*?

Do you know for a fact that they both have the same size? If
not, when MergeSort references array[1] it may actually access
iArray[2] (consider a system with 16-bit int and 32-bit pointers).

Do you know for a fact that the int values are valid for void*?
MerseSort does evaluate them as void* when it copies the values in and
out of aux.

> for(i=0; i < sizeOfArray; i++)
printf("%d ", iArray[i] );
printf("\n");
return 0;
}

Here is how I compile:
$ gcc -g -o mergesort mergesort.c

Here is the output:
$ ./mergesort
2 1 3 4 5 6 7 9 10 11 13 12 8 14

Clearly the output isn't completely sorted. Kindly help.

Regards
Kalyan

Remove del for email

[CBFalconer]

rkk wrote:

>
My mergesort program is below. There is a small piece of logical
error/bug in this code which I can't figure out, as a result the output
array isn't completely sorted. Requesting your help to resolve this
problem. Thanks in advance.

Arrays are easily handled with the standard qsort routine.
Mergesort is better suited for linked lists. You can find an
example of such in the wdfreq demo for hashlib. See the functions
splitlist, mergelists, mergesort. About 60 lines, including fairly
extensive commentary. The whole thing is available at:

<http://cbfalconer.home.att.net/download/>

--
Some useful references about C:
<http://www.ungerhu.com/jxh/clc.welcome.txt>
<http://www.eskimo.com/~scs/C-faq/top.html>
<http://benpfaff.org/writings/clc/off-topic.html>
<http://anubis.dkuug.dk/jtc1/sc22/wg14/www/docs/n869/(C99)
<http://www.dinkumware.com/refxc.html (C-library}
<http://gcc.gnu.org/onlinedocs/ (GNU docs)
<http://clc-wiki.net (C-info)