Merge Sort in C - array output is same as input after sort routine completes

[rkk]

Hi,

I have written a generic mergesort program which is as below:
---------------------------------------------------------
mergesort.h
-----------------------

void
MergeSort(void *array[],int p,int r,int elemSize,int(*C ompare)(const
void *keyA,const void *keyB));
void
Merge(void *array[],int p,int q, int r,int elemSize,int(*C ompare)(const
void *keyA,const void *keyB));
int
IntegerComp(con st void *keyA,const void *keyB);

mergesort.c
--------------------
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include "mergesort. h"
void
MergeSort(void *array[],int p,int r,int elemSize,int(*C ompare)(const
void *keyA,const void *keyB))
{
int q;
if(p < r) {
q = (p + r)/2;
MergeSort(array ,p,q,elemSize,C ompare);
MergeSort(array ,q + 1,r,elemSize,Co mpare);
Merge(array,p,q ,r,elemSize,Com pare);
}
}

void
Merge(void *array[],int p,int q, int r,int elemSize,int(*C ompare)(const
void *keyA,const void *keyB))
{
void **out = (void **)malloc(elemS ize * r);
int i,k,j;
i = k = p;
j = q + 1;
while( i <= q && j <= r ) {
if( Compare( &array[i * elemSize],&array[j * elemSize] ) <= 0 ) {
out[k++] = array[i++];
} else {
out[k++] = array[j++];
}
}
while( i <= q ) out[k++] = array[i++];
while( j <= r ) out[k++] = array[j++];

for (i = p;i < r; i++) {
array[i] = out[i];
}
free(out);
}
int
IntegerComp(con st void *keyA,const void *keyB)
{
if( (const int *) keyA == (const int *) keyB ) return 0;
else if( (const int *) keyA < (const int *) keyB ) return -1;
else if( (const int *) keyA (const int *) keyB ) return 1;
}
----------------------------------------------
And the driver program is here:
test.c
---------
#include <stdio.h>
#include "mergesort. h"

int
main()
{
int idx,length;
int arr[] = { 2,21,1,48,15,31 ,26 };
length = sizeof arr/sizeof &arr[0];

printf("Before sorting array:\n");
for (idx = 0;idx < length;idx++)
{
printf("%d ",arr[idx]);
}
printf("\n");

MergeSort(&arr, 0,length,sizeof (int),IntegerCo mp);

printf("After sorting array:\n");
for (idx = 0;idx < length;idx++)
{
printf("%d ",arr[idx]);
}
printf("\n");
return 0;
}
----------------------------------------------------------
I compile the programs above as:

gcc -g -o mergesort mergesort.c test.c

The output is little surprising as the array looks unsorted after sort
algorithm is completed. I am not understanding what's going wrong here,
kindly help me.:
kalyan@proteus mergesort
Before sorting array:
2 21 1 48 15 31 26
After sorting array:
2 21 1 48 15 31 26

Thank you.

Regards
Kalyan

[Richard Heathfield]

rkk said:

Hi,

I have written a generic mergesort program which is as below:

I took a long hard look at it, and got rid of many obvious bugs, which left
a not-so-obvious bug that I couldn't dislodge.

My best advice to you would be:

1) remove all casts - I guessed they were *all* wrong, and my guess was
correct
2) use void *, not void *[]
3) in Merge, use an unsigned char * to point at the base of the array
4) do your own pointer arithmetic properly (your code currently ignores the
problem of object sizes)
5) protect against malloc failure (returning, say, 0 if all went well and 1
if a memory allocation failure occurred)
6) write your comparison routine so that it doesn't need casts
7) choose better identifier names, names that reflect what the identifier
represents (e.g. you might want to use left, mid, and right, rather than p,
q, and r)

Once you have fixed all that up, you'll still have a bug. I couldn't find
that one, and wasn't heavily motivated to try. After applying all the
obvious fixes (see above), I got an output of

1 2 15 21 26 26 26

which is in some ways better and in some ways worse than your output.
Clearly, it has done some sorting - which is good! - but equally clearly it
has smeared one of the values across part of the array - which is not good.

So at least one bug remains. If you would like me to make my changes
available to you, just yell - but, as you can see, more work is required.

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at above domain (but drop the www, obviously)

[BRG]

Richard Heathfield wrote:

[snip]

Once you have fixed all that up, you'll still have a bug. I couldn't find
that one, and wasn't heavily motivated to try.

In addition to the issues you found, the convention on the end index for
an array partition seems suspect. In some places it appears that the
index for the last array element is being used while in other places it
seems that this top index refers to one element beyond the last element.

For example the line:

while( j <= r ) out[k++] = array[j++];

uses the array[r] element whereas the following line:

for (i = p; i < r; i++)

excludes this element.

It's quite possible that this is correct since I have not studied the
code in any detail. But it looks suspicious to me.

Brian Gladman

[Michael Mair]

rkk schrieb:

Hi,

I have written a generic mergesort program which is as below:
---------------------------------------------------------
mergesort.h
-----------------------

void
MergeSort(void *array[],int p,int r,int elemSize,int(*C ompare)(const
void *keyA,const void *keyB));
void
Merge(void *array[],int p,int q, int r,int elemSize,int(*C ompare)(const
void *keyA,const void *keyB));
int
IntegerComp(con st void *keyA,const void *keyB);

mergesort.c
--------------------
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include "mergesort. h"
void
MergeSort(void *array[],int p,int r,int elemSize,int(*C ompare)(const
void *keyA,const void *keyB))

Note: If you have an array of void*, then elemSize == sizeof (void*).
You probably want either an array of generic pointers which you
sort (an "index array") or an array of elements which you sort directly.
I will go for the latter even though it is not very efficient for
large elemSize.

{
int q;
if(p < r) {
q = (p + r)/2;
MergeSort(array ,p,q,elemSize,C ompare);
MergeSort(array ,q + 1,r,elemSize,Co mpare);

This suggests that p and r are valid indices.

Merge(array,p,q ,r,elemSize,Com pare);
}
}

void
Merge(void *array[],int p,int q, int r,int elemSize,int(*C ompare)(const
void *keyA,const void *keyB))

Same as above.

{
void **out = (void **)malloc(elemS ize * r);

No check whether this was successful.
You do not allocate the size you need which is
elemSize * (r- p + 1)

Note: One of the primary advantages of merge sort is that
you do not have to keep everything in memory. Allocating
a temp array leads that ad absurdum -- if a temp array is
allowed, then we can implement something more efficient...

int i,k,j;
i = k = p;

If you allocate only as much as you need, then k should start at 0.

j = q + 1;
while( i <= q && j <= r ) {
if( Compare( &array[i * elemSize],&array[j * elemSize] ) <= 0 ) {

You cannot calculate the address of the array members like this.
(unsigned char *)array + i * elemSize
is the correct way to do this.

out[k++] = array[i++];
} else {
out[k++] = array[j++];
}
}
while( i <= q ) out[k++] = array[i++];
while( j <= r ) out[k++] = array[j++];

for (i = p;i < r; i++) {
array[i] = out[i];
}
free(out);
}
int
IntegerComp(con st void *keyA,const void *keyB)
{
if( (const int *) keyA == (const int *) keyB ) return 0;
else if( (const int *) keyA < (const int *) keyB ) return -1;
else if( (const int *) keyA (const int *) keyB ) return 1;
}
----------------------------------------------
And the driver program is here:
test.c
---------
#include <stdio.h>
#include "mergesort. h"

int
main()
{
int idx,length;
int arr[] = { 2,21,1,48,15,31 ,26 };
length = sizeof arr/sizeof &arr[0];

sizeof arr / sizeof arr[0]

>
printf("Before sorting array:\n");
for (idx = 0;idx < length;idx++)
{
printf("%d ",arr[idx]);
}
printf("\n");

MergeSort(&arr, 0,length,sizeof (int),IntegerCo mp);

You have to pass "length - 1". If you write sizeof arr[0],
then you are on the safe side even if the type of arr changes.

>
printf("After sorting array:\n");
for (idx = 0;idx < length;idx++)
{
printf("%d ",arr[idx]);
}
printf("\n");
return 0;
}
----------------------------------------------------------
I compile the programs above as:

gcc -g -o mergesort mergesort.c test.c

gcc -std=c89 -pedantic -Wall -O test.c mergesort.c -o test

My changed version gives you some debug output; for this,
you need -DMY_DEBUG on the command line.

,-- mergesort.h --
#ifndef H_MERGE_SORT_H
#define H_MERGE_SORT_H

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

int
MergeSort (void *array,
int startIndex,
int endIndex,
int elemSize,
TCompareFcn Compare);

int
IntegerComp (const void *keyA,
const void *keyB);

#endif

`----
,-- test.c --
#include <stdio.h>
#include "mergesort. h"

int
main (void)
{
int idx, length;
int arr[] = { 2,21,1,48,15,31 ,26 };
length = sizeof arr / sizeof arr[0];

puts("Before sorting array:");
for (idx = 0; idx < length; idx++)
{
printf(" %d", arr[idx]);
}
putchar('\n');

if (!MergeSort(arr , 0, length - 1, sizeof arr[0], IntegerComp))
fputs("Merging not successful\n", stderr);

puts("After sorting array:");
for (idx = 0; idx < length; idx++)
{
printf(" %d", arr[idx]);
}
putchar('\n');
return 0;
}

`----
,-- mergesort.c --
#include "mergesort. h"

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

#ifdef MY_DEBUG
# include <stdio.h>
# define DEBUG_PRINT(s) printf s
# define DEBUG_I_PRINT(s ) printf("%*s", indent, " "), DEBUG_PRINT(s)
static int indent = 0;
# define DEBUG_ENTER indent += 3
# define DEBUG_EXIT indent -= 3
#else
# define DEBUG_PRINT(s)
# define DEBUG_I_PRINT(s )
# define DEBUG_ENTER
# define DEBUG_EXIT
#endif

static int
Merge (void *array,
int p,
int q,
int r,
int elemSize,
TCompareFcn Compare);

int
MergeSort (void *array,
int startIndex,
int endIndex,
int elemSize,
TCompareFcn Compare)
{
if (startIndex < endIndex) {
int splitIndex;
DEBUG_ENTER;
splitIndex = (startIndex + endIndex) / 2;

DEBUG_I_PRINT(( "MergeSort: %d %d\n", startIndex, splitIndex));
if (!MergeSort(arr ay,startIndex,s plitIndex,elemS ize,Compare))
return 0;
DEBUG_I_PRINT(( "MergeSort: %d %d\n", splitIndex+1, endIndex));
if (!MergeSort(arr ay,splitIndex + 1,endIndex,elem Size,Compare))
return 0;

DEBUG_I_PRINT(( "Merge: %d %d %d\n", startIndex, splitIndex, endIndex));
if (!Merge(array,s tartIndex,split Index,endIndex, elemSize,Compar e))
return 0;
DEBUG_EXIT;
}
return 1;
}

static int
Merge (void *array,
int startIndex,
int splitIndex,
int endIndex,
int elemSize,
TCompareFcn Compare)
{
int numElems = endIndex - startIndex + 1;
unsigned char *pTemp, *pCurrTemp;
unsigned char *pArrBase = array;
int lowerCurr = startIndex;
int upperCurr = splitIndex + 1;
const unsigned char *pArrLower = pArrBase + lowerCurr*elemS ize;
const unsigned char *pArrUpper = pArrBase + upperCurr*elemS ize;

pTemp = malloc(elemSize * numElems);
if (NULL == pTemp)
return 0;
pCurrTemp = pTemp;

DEBUG_ENTER;
while (lowerCurr <= splitIndex && upperCurr <= endIndex) {
DEBUG_I_PRINT(( "[%d(%d) %d(%d) -", lowerCurr, *(int*)pArrLowe r,
upperCurr, *(int*)pArrUppe r));
if ((*Compare)(pAr rLower, pArrUpper) <= 0 ) {
DEBUG_PRINT(("% d]\n", lowerCurr));
memcpy(pCurrTem p, pArrLower, elemSize);
pArrLower += elemSize;
++lowerCurr;
} else {
DEBUG_PRINT(("% d]\n", upperCurr));
memcpy(pCurrTem p, pArrUpper, elemSize);
pArrUpper += elemSize;
++upperCurr;
}
pCurrTemp += elemSize;
}
while (lowerCurr <= splitIndex ) {
DEBUG_I_PRINT(( "[%d(%d)]\n", lowerCurr, *(int*)pArrLowe r));
memcpy(pCurrTem p, pArrLower, elemSize);
pArrLower += elemSize;
++lowerCurr;
pCurrTemp += elemSize;
}
while (upperCurr <= endIndex) {
DEBUG_I_PRINT(( "[%d(%d)]\n", upperCurr, *(int*)pArrUppe r));
memcpy(pCurrTem p, pArrUpper, elemSize);
pArrUpper += elemSize;
++upperCurr;
pCurrTemp += elemSize;
}

memcpy(pArrBase + startIndex*elem Size, pTemp, elemSize * numElems);

free(pTemp);
DEBUG_EXIT;

return 1;
}
int
IntegerComp(con st void *keyA, const void *keyB)
{
const int *pIntKeyA = keyA;
const int *pIntKeyB = keyB;

return (*pIntKeyA *pIntKeyB) - (*pIntKeyA < *pIntKeyB);
}

`----

Cheers
Michael
--
E-Mail: Mine is an /at/ gmx /dot/ de address.

[Richard Heathfield]

BRG said:

<snip>

For example the line:

while( j <= r ) out[k++] = array[j++];

uses the array[r] element whereas the following line:

for (i = p; i < r; i++)

excludes this element.

Ah, thank you, Brian. Good spot. Together with my other fixes, that is
sufficient that the OP's sample array is correctly sorted, as is a second
test array I tried.

All that remains is to see whether he is sufficiently interested in his own
problem to request me to post my fixes. :-)
--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at above domain (but drop the www, obviously)

[CBFalconer]

Michael Mair wrote:

rkk schrieb:

>I have written a generic mergesort program which is as below:

.... snip ...

>
Note: One of the primary advantages of merge sort is that
you do not have to keep everything in memory. Allocating
a temp array leads that ad absurdum -- if a temp array is
allowed, then we can implement something more efficient...

Mergesort is primarily useful in dealing with linked lists or
monstrous files, where its stability and ability to handle
arbitrary length lists are very helpful.

--
Some informative links:
news:news.annou nce.newusers
http://www.geocities.com/nnqweb/
http://www.catb.org/~esr/faqs/smart-questions.html
http://www.caliburn.nl/topposting.html
http://www.netmeister.org/news/learn2quote.html

--
Posted via a free Usenet account from http://www.teranews.com

[rkk]

Sorry for late response.

I do understand the mistakes I did in my version of program. Shortly I
will post my own corrected version.

Also Thanks to Michael for his mergesort code. It is really helpful.
Much appreciated.

One doubt I have is that to calculate the mem address of array why it
has to be casted to unsigned char * why cant char* instead? Sorry to
ask this very silly question here.

Many thanks for all of your help.

Regards
Kalyan

Richard Heathfield wrote:

BRG said:

<snip>

For example the line:

while( j <= r ) out[k++] = array[j++];

uses the array[r] element whereas the following line:

for (i = p; i < r; i++)

excludes this element.

Ah, thank you, Brian. Good spot. Together with my other fixes, that is
sufficient that the OP's sample array is correctly sorted, as is a second
test array I tried.

All that remains is to see whether he is sufficiently interested in his own
problem to request me to post my fixes. :-)
--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at above domain (but drop the www, obviously)

[rkk]

Michael, Many thanks for this piece of code.

Regards
Kalyan

Michael Mair wrote:

rkk schrieb:

Hi,

I have written a generic mergesort program which is as below:
---------------------------------------------------------
mergesort.h
-----------------------

void
MergeSort(void *array[],int p,int r,int elemSize,int(*C ompare)(const
void *keyA,const void *keyB));
void
Merge(void *array[],int p,int q, int r,int elemSize,int(*C ompare)(const
void *keyA,const void *keyB));
int
IntegerComp(con st void *keyA,const void *keyB);

mergesort.c
--------------------
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include "mergesort. h"
void
MergeSort(void *array[],int p,int r,int elemSize,int(*C ompare)(const
void *keyA,const void *keyB))

Note: If you have an array of void*, then elemSize == sizeof (void*).
You probably want either an array of generic pointers which you
sort (an "index array") or an array of elements which you sort directly.
I will go for the latter even though it is not very efficient for
large elemSize.

{
int q;
if(p < r) {
q = (p + r)/2;
MergeSort(array ,p,q,elemSize,C ompare);
MergeSort(array ,q + 1,r,elemSize,Co mpare);

This suggests that p and r are valid indices.

Merge(array,p,q ,r,elemSize,Com pare);
}
}

void
Merge(void *array[],int p,int q, int r,int elemSize,int(*C ompare)(const
void *keyA,const void *keyB))

Same as above.

{
void **out = (void **)malloc(elemS ize * r);

No check whether this was successful.
You do not allocate the size you need which is
elemSize * (r- p + 1)

Note: One of the primary advantages of merge sort is that
you do not have to keep everything in memory. Allocating
a temp array leads that ad absurdum -- if a temp array is
allowed, then we can implement something more efficient...

int i,k,j;
i = k = p;

If you allocate only as much as you need, then k should start at 0.

j = q + 1;
while( i <= q && j <= r ) {
if( Compare( &array[i * elemSize],&array[j * elemSize] ) <= 0 ) {

You cannot calculate the address of the array members like this.
(unsigned char *)array + i * elemSize
is the correct way to do this.

out[k++] = array[i++];
} else {
out[k++] = array[j++];
}
}
while( i <= q ) out[k++] = array[i++];
while( j <= r ) out[k++] = array[j++];

for (i = p;i < r; i++) {
array[i] = out[i];
}
free(out);
}
int
IntegerComp(con st void *keyA,const void *keyB)
{
if( (const int *) keyA == (const int *) keyB ) return 0;
else if( (const int *) keyA < (const int *) keyB ) return -1;
else if( (const int *) keyA (const int *) keyB ) return 1;
}
----------------------------------------------
And the driver program is here:
test.c
---------
#include <stdio.h>
#include "mergesort. h"

int
main()
{
int idx,length;
int arr[] = { 2,21,1,48,15,31 ,26 };
length = sizeof arr/sizeof &arr[0];

sizeof arr / sizeof arr[0]

printf("Before sorting array:\n");
for (idx = 0;idx < length;idx++)
{
printf("%d ",arr[idx]);
}
printf("\n");

MergeSort(&arr, 0,length,sizeof (int),IntegerCo mp);

You have to pass "length - 1". If you write sizeof arr[0],
then you are on the safe side even if the type of arr changes.

printf("After sorting array:\n");
for (idx = 0;idx < length;idx++)
{
printf("%d ",arr[idx]);
}
printf("\n");
return 0;
}
----------------------------------------------------------
I compile the programs above as:

gcc -g -o mergesort mergesort.c test.c

gcc -std=c89 -pedantic -Wall -O test.c mergesort.c -o test

My changed version gives you some debug output; for this,
you need -DMY_DEBUG on the command line.

,-- mergesort.h --
#ifndef H_MERGE_SORT_H
#define H_MERGE_SORT_H

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

int
MergeSort (void *array,
int startIndex,
int endIndex,
int elemSize,
TCompareFcn Compare);

int
IntegerComp (const void *keyA,
const void *keyB);

#endif

`----
,-- test.c --
#include <stdio.h>
#include "mergesort. h"

int
main (void)
{
int idx, length;
int arr[] = { 2,21,1,48,15,31 ,26 };
length = sizeof arr / sizeof arr[0];

puts("Before sorting array:");
for (idx = 0; idx < length; idx++)
{
printf(" %d", arr[idx]);
}
putchar('\n');

if (!MergeSort(arr , 0, length - 1, sizeof arr[0], IntegerComp))
fputs("Merging not successful\n", stderr);

puts("After sorting array:");
for (idx = 0; idx < length; idx++)
{
printf(" %d", arr[idx]);
}
putchar('\n');
return 0;
}

`----
,-- mergesort.c --
#include "mergesort. h"

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

#ifdef MY_DEBUG
# include <stdio.h>
# define DEBUG_PRINT(s) printf s
# define DEBUG_I_PRINT(s ) printf("%*s", indent, " "), DEBUG_PRINT(s)
static int indent = 0;
# define DEBUG_ENTER indent += 3
# define DEBUG_EXIT indent -= 3
#else
# define DEBUG_PRINT(s)
# define DEBUG_I_PRINT(s )
# define DEBUG_ENTER
# define DEBUG_EXIT
#endif

static int
Merge (void *array,
int p,
int q,
int r,
int elemSize,
TCompareFcn Compare);

int
MergeSort (void *array,
int startIndex,
int endIndex,
int elemSize,
TCompareFcn Compare)
{
if (startIndex < endIndex) {
int splitIndex;
DEBUG_ENTER;
splitIndex = (startIndex + endIndex) / 2;

DEBUG_I_PRINT(( "MergeSort: %d %d\n", startIndex, splitIndex));
if (!MergeSort(arr ay,startIndex,s plitIndex,elemS ize,Compare))
return 0;
DEBUG_I_PRINT(( "MergeSort: %d %d\n", splitIndex+1, endIndex));
if (!MergeSort(arr ay,splitIndex + 1,endIndex,elem Size,Compare))
return 0;

DEBUG_I_PRINT(( "Merge: %d %d %d\n", startIndex, splitIndex, endIndex));
if (!Merge(array,s tartIndex,split Index,endIndex, elemSize,Compar e))
return 0;
DEBUG_EXIT;
}
return 1;
}

static int
Merge (void *array,
int startIndex,
int splitIndex,
int endIndex,
int elemSize,
TCompareFcn Compare)
{
int numElems = endIndex - startIndex + 1;
unsigned char *pTemp, *pCurrTemp;
unsigned char *pArrBase = array;
int lowerCurr = startIndex;
int upperCurr = splitIndex + 1;
const unsigned char *pArrLower = pArrBase + lowerCurr*elemS ize;
const unsigned char *pArrUpper = pArrBase + upperCurr*elemS ize;

pTemp = malloc(elemSize * numElems);
if (NULL == pTemp)
return 0;
pCurrTemp = pTemp;

DEBUG_ENTER;
while (lowerCurr <= splitIndex && upperCurr <= endIndex) {
DEBUG_I_PRINT(( "[%d(%d) %d(%d) -", lowerCurr, *(int*)pArrLowe r,
upperCurr, *(int*)pArrUppe r));
if ((*Compare)(pAr rLower, pArrUpper) <= 0 ) {
DEBUG_PRINT(("% d]\n", lowerCurr));
memcpy(pCurrTem p, pArrLower, elemSize);
pArrLower += elemSize;
++lowerCurr;
} else {
DEBUG_PRINT(("% d]\n", upperCurr));
memcpy(pCurrTem p, pArrUpper, elemSize);
pArrUpper += elemSize;
++upperCurr;
}
pCurrTemp += elemSize;
}
while (lowerCurr <= splitIndex ) {
DEBUG_I_PRINT(( "[%d(%d)]\n", lowerCurr, *(int*)pArrLowe r));
memcpy(pCurrTem p, pArrLower, elemSize);
pArrLower += elemSize;
++lowerCurr;
pCurrTemp += elemSize;
}
while (upperCurr <= endIndex) {
DEBUG_I_PRINT(( "[%d(%d)]\n", upperCurr, *(int*)pArrUppe r));
memcpy(pCurrTem p, pArrUpper, elemSize);
pArrUpper += elemSize;
++upperCurr;
pCurrTemp += elemSize;
}

memcpy(pArrBase + startIndex*elem Size, pTemp, elemSize * numElems);

free(pTemp);
DEBUG_EXIT;

return 1;
}
int
IntegerComp(con st void *keyA, const void *keyB)
{
const int *pIntKeyA = keyA;
const int *pIntKeyB = keyB;

return (*pIntKeyA *pIntKeyB) - (*pIntKeyA < *pIntKeyB);
}

`----

Cheers
Michael
--
E-Mail: Mine is an /at/ gmx /dot/ de address.

[Michael Mair]

Please do not top-post.
Your reply belongs below (or interspersed with) the text you
are replying to; you of course can and should snip whatever
you find not useful for the parts you want to discuss further.

rkk schrieb:

Richard Heathfield wrote:

>>BRG said:

<snip: inconsistent use of the top index (included/excluded)

>>
Ah, thank you, Brian. Good spot. Together with my other fixes, that is
sufficient that the OP's sample array is correctly sorted, as is a second
test array I tried.

All that remains is to see whether he is sufficiently interested in his own
problem to request me to post my fixes. :-)

Sorry for late response.

I do understand the mistakes I did in my version of program. Shortly I
will post my own corrected version.

Also Thanks to Michael for his mergesort code. It is really helpful.
Much appreciated.

I am happy to hear that :-)
Note that this was only an example implementation of one of the
two possible solutions and not the one I would actually implement.

One doubt I have is that to calculate the mem address of array why it
has to be casted to unsigned char * why cant char* instead? Sorry to
ask this very silly question here.

Not a silly question at all.

Even though void * has the same representation and alignment
requirements as a pointer to any of the three types of char,
you cannot do pointer arithmetic with it.
[Three types of char? char is special in that there is a difference
between signed char and "plain" char which is a type distinct from
both signed char and unsigned char but has the characteristics of
one of these.]
unsigned char * is the only type with which you can guaranteedly
access the representation (i.e. the underlying bit pattern) of any
object:
myType foo;
void *pFoo = &foo;
unsigned char *bar = pFoo;
int i;

/* assign value to foo */
....

for (i = 0; i < sizeof foo; ++i) {
printf("%x\t", (unsigned int) bar[i]);
}
putchar('\n');
will give you the bytes of foo.
Neither char * nor signed char * guaranteedly can give you that.
Thus, you use "char" for characters and "unsigned char" if you
mean bytes and want to calculate addresses.

The comp.lang.c FAQ tells you a little bit more about that:
http://c-faq.com
Cheers
Michael
--
E-Mail: Mine is an /at/ gmx /dot/ de address.

[CBFalconer]

rkk wrote:

>

.... snip ...

>
One doubt I have is that to calculate the mem address of array why
it has to be casted to unsigned char * why cant char* instead?
Sorry to ask this very silly question here.

Please don't top-post. Your answer belongs after, or possibly
intermixed with, the material you quote, after snipping. See the
links in my sig. below.

You cast to unsigned char because your system may define char as
either signed or unsigned. Without the cast the code is not
portable. Many routines (e.g. toupper() etc.) require unsigned
chars.

--
Some informative links:
<news:news.anno unce.newusers
<http://www.geocities.c om/nnqweb/>
<http://www.catb.org/~esr/faqs/smart-questions.html>
<http://www.caliburn.nl/topposting.html >
<http://www.netmeister. org/news/learn2quote.htm l>
<http://cfaj.freeshell. org/google/>