Hi.

Basically I first made some code to do mergesort on a list of numbers. Worked like a champ. Then I said, what the heck, why not do a mergesort on an array of structs, this is where it gets a little funky. While the first sort of the data works fine it goes to the number sort and starts to screw up. It'll sort the numbers but mix up the data in the fields! I don't have a clue as to what causes the mix up, anyone got any ideas as to what is causing this?

example of messing up:

jeff, 45 lou, 25 bob, 35 calv, 27 mel, 56 tom, 12 jim, 72 matt, 65 sean, 32 phil, 87
bob, 35 calv, 27 jim, 72 jeff, 45 lou, 25 matt, 65 mel, 56 phil, 87 sean, 32 tom, 12
bob, 87 sean, 72 jeff, 65 mel, 56 phil, 45 lou, 35 calv, 32 tom, 27 jim, 25 matt, 12

/*the code*/
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

typedef char byte;

struct info {
  char name[6];
  int age;
} ;

void memcopy( byte *to, byte *from, int count ) {

  while ( count-- > 0 ) *to++ = *from++ ;

}

int charcomp(  byte *a , byte *b ) {

  char *x, *y ;

  x = (char*)a ;

  y = (char*)b ;

  if ( *x > *y ) return 1 ;

  if ( *x == *y ) return 0 ;

  return -1 ;

}
int intcomp(  byte *a , byte *b ) {

  int *x, *y ;

  x = (int*)a ;

  y = (int*)b ;

  if ( *x < *y ) return 1 ;

  if ( *x == *y ) return 0 ;

  return -1 ;

}

void merge_sort( byte data[], int n, int elementsize, int (*p_cmp_f)( ) ) ;
int main( int argc, char *argv[] ) {
  char buffer[6];
  int age,i,count;

  FILE *fin = fopen(argv[1],"r");

  struct info people[20];
  for(i=0;i<20;i++){
    if( fscanf(fin,"%s %d",buffer,&age)==EOF)break;
    memcopy(people[i].name,buffer,6);
    people[i].age=age;
    count++;
  }


  for(i=0;i<count;i++){
    printf("%s, %d ",people[i].name,people[i].age);
  }

  printf("\n");

  merge_sort((byte*)&people->name,count,sizeof(struct info),charcomp);

  for(i=0;i<count;i++){
    printf("%s, %d ",people[i].name,people[i].age);
  }

  printf("\n");
  fclose(fin);
  return 0;
}

void merge_sort( byte data[], int n, int elementsize, int (*p_cmp_f)( ) )  {

  byte *firsthalf, *endoffirsthalf, *secondhalf, *endofsecondhalf, *resultbuffer, *p_result ;

  int halfsize ;

  if (n <= 1 ) return ;

  halfsize = n / 2 ;

  firsthalf = data ;

  secondhalf = data + halfsize * elementsize ;

  merge_sort( firsthalf, halfsize, elementsize, p_cmp_f ) ;
  merge_sort( secondhalf, n - halfsize, elementsize, p_cmp_f ) ;

  endoffirsthalf = secondhalf ;

  endofsecondhalf = data + n * elementsize ;

  resultbuffer = (byte*) malloc( n * elementsize ) ;

  p_result = resultbuffer ;

  while( firsthalf < endoffirsthalf && secondhalf < endofsecondhalf ) {

    if( (*p_cmp_f)( firsthalf, secondhalf ) < 0 ) {

      memcopy( p_result, firsthalf, elementsize ) ;
      firsthalf += elementsize ;

    }

    else {

      memcopy( p_result, secondhalf, elementsize ) ;
      secondhalf += elementsize ;

    }

    p_result += elementsize ;

  }

  while( firsthalf < endoffirsthalf ) {

    memcopy( p_result, firsthalf, elementsize ) ;
    firsthalf += elementsize ;
    p_result += elementsize ;

  }

  while( secondhalf < endofsecondhalf ) {

    memcopy( p_result, secondhalf, elementsize ) ;
    secondhalf += elementsize ;
    p_result += elementsize ;

  }

  memcopy( data, resultbuffer, n * elementsize ) ;

  free(resultbuffer) ;

}
merge_sort((byte*)&people->name,count,sizeof(struct info),charcomp);

This is not correct. Check what are the parameters you are sending.

The prototype of the function should have been something like

void merge_sort( struct info data[], int n, int (*p_cmp_f)( ) ) ;

And you should add another comparison function for comparing string.

This article has been dead for over six months. Start a new discussion instead.