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

Discussion in 'C Programming' started by rkk, Sep 22, 2006.

  1. rkk

    rkk Guest

    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(*Compare)(const
    void *keyA,const void *keyB));
    void
    Merge(void *array[],int p,int q, int r,int elemSize,int(*Compare)(const
    void *keyA,const void *keyB));
    int
    IntegerComp(const 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(*Compare)(const
    void *keyA,const void *keyB))
    {
    int q;
    if(p < r) {
    q = (p + r)/2;
    MergeSort(array,p,q,elemSize,Compare);
    MergeSort(array,q + 1,r,elemSize,Compare);
    Merge(array,p,q,r,elemSize,Compare);
    }
    }

    void
    Merge(void *array[],int p,int q, int r,int elemSize,int(*Compare)(const
    void *keyA,const void *keyB))
    {
    void **out = (void **)malloc(elemSize * 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 = out;
    }
    free(out);
    }


    int
    IntegerComp(const 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),IntegerComp);

    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
    rkk, Sep 22, 2006
    #1
    1. Advertising

  2. 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)
    Richard Heathfield, Sep 22, 2006
    #2
    1. Advertising

  3. rkk

    BRG Guest

    Re: Merge Sort in C - array output is same as input after sort routinecompletes

    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
    BRG, Sep 22, 2006
    #3
  4. rkk

    Michael Mair Guest

    Re: Merge Sort in C - array output is same as input after sort routinecompletes

    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(*Compare)(const
    > void *keyA,const void *keyB));
    > void
    > Merge(void *array[],int p,int q, int r,int elemSize,int(*Compare)(const
    > void *keyA,const void *keyB));
    > int
    > IntegerComp(const 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(*Compare)(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,Compare);
    > MergeSort(array,q + 1,r,elemSize,Compare);


    This suggests that p and r are valid indices.

    > Merge(array,p,q,r,elemSize,Compare);
    > }
    > }
    >
    > void
    > Merge(void *array[],int p,int q, int r,int elemSize,int(*Compare)(const
    > void *keyA,const void *keyB))


    Same as above.

    > {
    > void **out = (void **)malloc(elemSize * 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 = out;
    > }
    > free(out);
    > }
    >
    >
    > int
    > IntegerComp(const 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),IntegerComp);


    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(array,startIndex,splitIndex,elemSize,Compare))
    return 0;
    DEBUG_I_PRINT(("MergeSort: %d %d\n", splitIndex+1, endIndex));
    if (!MergeSort(array,splitIndex + 1,endIndex,elemSize,Compare))
    return 0;

    DEBUG_I_PRINT(("Merge: %d %d %d\n", startIndex, splitIndex, endIndex));
    if (!Merge(array,startIndex,splitIndex,endIndex,elemSize,Compare))
    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*elemSize;
    const unsigned char *pArrUpper = pArrBase + upperCurr*elemSize;

    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*)pArrLower,
    upperCurr, *(int*)pArrUpper));
    if ((*Compare)(pArrLower, pArrUpper) <= 0 ) {
    DEBUG_PRINT(("%d]\n", lowerCurr));
    memcpy(pCurrTemp, pArrLower, elemSize);
    pArrLower += elemSize;
    ++lowerCurr;
    } else {
    DEBUG_PRINT(("%d]\n", upperCurr));
    memcpy(pCurrTemp, pArrUpper, elemSize);
    pArrUpper += elemSize;
    ++upperCurr;
    }
    pCurrTemp += elemSize;
    }
    while (lowerCurr <= splitIndex ) {
    DEBUG_I_PRINT(("[%d(%d)]\n", lowerCurr, *(int*)pArrLower));
    memcpy(pCurrTemp, pArrLower, elemSize);
    pArrLower += elemSize;
    ++lowerCurr;
    pCurrTemp += elemSize;
    }
    while (upperCurr <= endIndex) {
    DEBUG_I_PRINT(("[%d(%d)]\n", upperCurr, *(int*)pArrUpper));
    memcpy(pCurrTemp, pArrUpper, elemSize);
    pArrUpper += elemSize;
    ++upperCurr;
    pCurrTemp += elemSize;
    }

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

    free(pTemp);
    DEBUG_EXIT;

    return 1;
    }


    int
    IntegerComp(const 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, Sep 22, 2006
    #4
  5. 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)
    Richard Heathfield, Sep 23, 2006
    #5
  6. rkk

    CBFalconer Guest

    Re: Merge Sort in C - array output is same as input after sortroutinecompletes

    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.announce.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
    CBFalconer, Sep 23, 2006
    #6
  7. rkk

    rkk Guest

    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, Sep 24, 2006
    #7
  8. rkk

    rkk Guest

    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(*Compare)(const
    > > void *keyA,const void *keyB));
    > > void
    > > Merge(void *array[],int p,int q, int r,int elemSize,int(*Compare)(const
    > > void *keyA,const void *keyB));
    > > int
    > > IntegerComp(const 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(*Compare)(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,Compare);
    > > MergeSort(array,q + 1,r,elemSize,Compare);

    >
    > This suggests that p and r are valid indices.
    >
    > > Merge(array,p,q,r,elemSize,Compare);
    > > }
    > > }
    > >
    > > void
    > > Merge(void *array[],int p,int q, int r,int elemSize,int(*Compare)(const
    > > void *keyA,const void *keyB))

    >
    > Same as above.
    >
    > > {
    > > void **out = (void **)malloc(elemSize * 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 = out;
    > > }
    > > free(out);
    > > }
    > >
    > >
    > > int
    > > IntegerComp(const 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),IntegerComp);

    >
    > 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(array,startIndex,splitIndex,elemSize,Compare))
    > return 0;
    > DEBUG_I_PRINT(("MergeSort: %d %d\n", splitIndex+1, endIndex));
    > if (!MergeSort(array,splitIndex + 1,endIndex,elemSize,Compare))
    > return 0;
    >
    > DEBUG_I_PRINT(("Merge: %d %d %d\n", startIndex, splitIndex, endIndex));
    > if (!Merge(array,startIndex,splitIndex,endIndex,elemSize,Compare))
    > 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*elemSize;
    > const unsigned char *pArrUpper = pArrBase + upperCurr*elemSize;
    >
    > 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*)pArrLower,
    > upperCurr, *(int*)pArrUpper));
    > if ((*Compare)(pArrLower, pArrUpper) <= 0 ) {
    > DEBUG_PRINT(("%d]\n", lowerCurr));
    > memcpy(pCurrTemp, pArrLower, elemSize);
    > pArrLower += elemSize;
    > ++lowerCurr;
    > } else {
    > DEBUG_PRINT(("%d]\n", upperCurr));
    > memcpy(pCurrTemp, pArrUpper, elemSize);
    > pArrUpper += elemSize;
    > ++upperCurr;
    > }
    > pCurrTemp += elemSize;
    > }
    > while (lowerCurr <= splitIndex ) {
    > DEBUG_I_PRINT(("[%d(%d)]\n", lowerCurr, *(int*)pArrLower));
    > memcpy(pCurrTemp, pArrLower, elemSize);
    > pArrLower += elemSize;
    > ++lowerCurr;
    > pCurrTemp += elemSize;
    > }
    > while (upperCurr <= endIndex) {
    > DEBUG_I_PRINT(("[%d(%d)]\n", upperCurr, *(int*)pArrUpper));
    > memcpy(pCurrTemp, pArrUpper, elemSize);
    > pArrUpper += elemSize;
    > ++upperCurr;
    > pCurrTemp += elemSize;
    > }
    >
    > memcpy(pArrBase + startIndex*elemSize, pTemp, elemSize * numElems);
    >
    > free(pTemp);
    > DEBUG_EXIT;
    >
    > return 1;
    > }
    >
    >
    > int
    > IntegerComp(const 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.
    rkk, Sep 24, 2006
    #8
  9. rkk

    Michael Mair Guest

    Re: Merge Sort in C - array output is same as input after sort routinecompletes

    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);
    }
    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.
    Michael Mair, Sep 24, 2006
    #9
  10. rkk

    CBFalconer Guest

    Re: Merge Sort in C - array output is same as input after sort routinecompletes

    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.announce.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>
    <http://cfaj.freeshell.org/google/>
    CBFalconer, Sep 24, 2006
    #10
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. joeted
    Replies:
    0
    Views:
    313
    joeted
    Apr 21, 2004
  2. Brian Gordaychik
    Replies:
    6
    Views:
    17,034
    John Saunders
    Dec 6, 2004
  3. Replies:
    8
    Views:
    39,668
    Roedy Green
    Oct 13, 2005
  4. Basman
    Replies:
    0
    Views:
    415
    Basman
    Oct 29, 2007
  5. abhi
    Replies:
    0
    Views:
    350
Loading...

Share This Page