Thread: sorting using pointer to pointer not working

Hi,

I need to sort an array of structures by a structure member.
Sorting the array elements directly works fine, but is not fast enough.
So I re-wrote the merge sort routine to use an array of pointers pointing to the structures, and want to sort the pointers.
This doesn't work. The pointers don't get sorted to point to the structures in aascending order of the member value.
The sort does change the pointer values, but they don't get sorted by anything as far as I can see.

Below is the part of the code that should be enough to test the problem.

Code:

// **** Declarations ****

#define BY_SEQNUM   0  // which  struct member to sort by
#define BY_GENID    1
#define BY_LEN      2

#define SOMENUMBER   50   // used in main() for initialization

struct resultnode{
    unsigned long seq_num;
    unsigned long len;
    unsigned long Generation_ID;
    unsigned long generation_member_count;
};
typedef resultnode result;

result *Results;
result **r_pt_by_SeqNum;
unsigned long resultcount;

// **** merge sort routine ***

int SortResults(result **ptpt, unsigned long thismany, int sorttype)
{
    void partitioning(result **, unsigned long, unsigned long, int);
    partitioning(ptpt, 0L, thismany, sorttype);
    return(0);
}

void partitioning(result **ptpt, unsigned long low, unsigned long high, int sorttype)
{
    void msort_test1(result **ptpt, unsigned long low, unsigned long mid, unsigned long high);
    void msort_test2(result **ptpt, unsigned long low, unsigned long mid, unsigned long high);  // not used in this test
    void msort_test3(result **ptpt, unsigned long low, unsigned long mid, unsigned long high);  // not used in this test
    void partitioning(result **ptpt, unsigned long, unsigned long, int);

    unsigned long mid;
    if(low < high){
        mid = (low + high)/2;
        partitioning(ptpt, low, mid, sorttype);
        partitioning(ptpt, mid+1, high, sorttype);

        if(sorttype == BY_SEQNUM)
            msort_test1(ptpt, low, mid, high);  // this is the one tested here
        else if(sorttype == BY_GENID)
             msort_test2(ptpt, low, mid, high);
        else if(sorttype == BY_LEN)
            msort_test3(ptpt, low, mid, high);
        else{ printf("Internal error\n"); exit(-1); }
    }
}

void msort_test1(result **ptpt, unsigned long low, unsigned long mid, unsigned long high)
{
    unsigned long i,j,k,l;
    result **b;

    b = (result **)malloc(resultcount * sizeof(result *));
    if( b == NULL ){
        printf("Mem alloc error\n");
        exit(-1);
    }

    l = low;
    i = low;
    j = mid+1;
    while( (l <= mid) && (j <= high) ){
        if( (*ptpt[l]).seq_num <= (*ptpt[j]).seq_num ){
            b[i] = ptpt[l];
            l++;
        }
        else
        {
            b[i] = ptpt[j];
            j++;
        }
        i++;
   }
    if(l > mid){
        for(k = j; k <= high; k++){
            b[i] = ptpt[k];
            i++;
        }
    }
    else{
        for(k=l; k <= mid; k++){
            b[i] = ptpt[k];
            i++;
        }
    }
    for(k = low; k <= high; k++){
        ptpt[k] = b[k];
    }
    free ( b );
}

// ***some main stuff (I hope it'"s enough) to run the above ***
main()
{
    int SortResults(result **, unsigned long,  int);
    unsigned i;

    resultcount = SOMENUMBER;

    Results = (result *)malloc(resultcount * sizeof(result));
    if( Results == NULL ){
        printf("Not enough memory.\n");
        exit(-1);
    }

    for( i = 0; i < resultcount; i++)
        Results[i].seq_num = resultcount - i;  // to get seq_num reverse-sorted for the test
    
    r_pt_by_SeqNum = (result **)malloc(resultcount * sizeof(result *));

    for(i = 0; i < resultcount; i++)    // initialize pointer array
       r_pt_by_SeqNum[i] = &Results[i]; 

    SortResults(r_pt_by_SeqNum, resultcount - 1L, BY_SEQNUM);  //  // HERE WE GO

    // AND IT DOESN'T SORT...
}

// **** End of code ****
// *********************

I am totally stumped with this...

Any help greatly appreciated.