mergesort

[Dewey1040]

Ok i know this has all sorts of issues, im getting tons of errors, any suggestion on where to start?

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

typdef char byte;

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

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

}

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

  if( *a == *b ) return( 1 );
  else return( 0 );

}

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

int main( int argc, char *argv[] ) {

  int A[500000] ;
  int n , i ;

  n = atoi( argv[1] ) ;

  for ( i = 0 ; i <= n ; i++ ) A[i] = rand() % 10000 ;

  for ( i = 0 ; i <= 19 ; i++ ) printf(" %d ", A[i] ) ;
  printf("\n") ;

  merge_sort( (byte *) A, n , sizeof(int) , compare ) ;

  printf("\n") ;
  for ( i = 0 ; i <= 19 ; i++ ) printf(" %d ", A[i] ) ;
  printf("\n") ;

  return 0 ;

}

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

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

  if( n <= 1 )
    return;

  halfsize = n/2;
  firsthalf = data;
  secondhalf = data + halfisze * elementsize;

  mergesort( firsthalf, halfisze, elementsize, p_cmp_f );
  mergesort( 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 ){
      memcpy( p_result, firsthalf, elementsize );
      firsthalf += elementsize;
    } else {
      memcpy( p_result, secondhalf, elementsize );
      secondhalf += elementsize;
    }
    p_result += elementsize;
  }
  while( firsthalf < endoffirsthalf ){
    memcpy( p_result, firsthalf, elementsize );
    firsthalf += elementsize;
    p_result += elementsize;
  }
  while( secondhalf < endofsecondhalf ){
    memcpy( p_result, secondhalf, elementsize );
    secondhalf += elementsize;
    p_result += elementsize;
  }
  memcpy( data, resultbuffer, n * elementsize );
  free( resultbuffer );
}


}

[s_sridhar]

Why do you make simple things look complex???
Let mergesort be the driver to the sorting routine taking arguments the array and it's size. Here a temporary array is allocated and passed to the msort routine, and changes are initially carried out to the msort routine. msort takes the array, temporary array, leftposition and right position.
msort will be as follows

void msort
{
centre=(left+right)/2;
msort(tmparray,n,left,centre);
msort(tmparray,n,centre,right);/*recursively calling msort for dividing and conquer strategy */
merge(tmparray,leftpos, centre,right)
/*Merge is the routine to merge two sorted arrays in sorted order */
}

This may have some issues but definitely more clear than yours!!! Instead of pointers if you use index, it will be better

[ArkM]

>any suggestion on where to start?
Start from http://eternallyconfuzzled.com/tuts/algorithms/jsw_tut_sorting.aspx#merge

[Narue]

>im getting tons of errors, any suggestion on where to start?
If you're getting tons of errors, then that means you cranked out code all in one sitting without compiling or testing. That's the express train to crappycodeville. Write a little, test it, write a little, test it. Not only does that process keep your code well modularized, it also saves you from drowning in a flood of errors.

I don't know you could make it such a complex one.....
Here's the solution that I referenced it through the MergeSort algorithm..........

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

void getdata(int arr[],int n)
{
 int i;
  printf("\n Enter the data:\n");
  for(i=0;i<n;i++)
    {
     scanf("%d",&arr[i]);
    }
}

void display(int arr[],int n)
{
 int i;
 printf("\n The sorted array is...");
 printf("\n\n");
 for(i=0;i<n;i++)
    {
     printf("\narr[%d]--->%d ",i+1,arr[i]);
    }
 getchar();
}

void sort(int arr[],int low,int mid,int high)
{
 int i,j,k,l,b[20];
 l=low;
 i=low;
 j=mid+1;
 while((l<=mid)&&(j<=high))
   {
    if(arr[l]<=arr[j])
      {
       b[i]=arr[l];
       l++;
      }
    else
      {
       b[i]=arr[j];
       j++;
      }
    i++;
   }
 if(l>mid)
   {
    for(k=j;k<=high;k++)
       {
        b[i]=arr[k];
        i++;
       }
   }
 else
   {
    for(k=l;k<=mid;k++)
       {
        b[i]=arr[k];
        i++;
       }
   }
 for(k=low;k<=high;k++)
    {
     arr[k]=b[k];
    }
}

void partition(int arr[],int low,int high)
{
 int mid,k=0;
 if(low<high)
   {
    mid=(low+high)/2;
    partition(arr,low,mid);
    partition(arr,mid+1,high);
    sort(arr,low,mid,high);
   }
	printf("\n");
	for(k=low;k<=high;k++)
	printf(" %d",arr[k]);
}


int main()
{
 int arr[20];
 int n;
 printf(" Enter number of elements\n");
 scanf("%d",&n);
 getdata(arr,n);
 partition(arr,0,n-1);
 display(arr,n);
 getchar();
 return 0;
}

SNIP

[Dewey1040]

thanks to everyone, arkM thats link is useful, cuz it helps with radix sort as well. and thanks dmachop for that code

[ArkM]

>arkM thats link is useful...
Don't mention it. Thank Narue for that link ;)

[Dewey1040]

so i thought this was solved, but i edited the code a little, now i get seg fault heres the code... if anybody can help please help before 8 in the morning for i have a final in computing which includes mergesort

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

void display(int arr[],int n) {
  int i;
  printf("\n The sorted array is...");
  printf("\n\n");

  for( i = 0; i < n; i++ ){
      printf("\narr[%d]--->%d ",i+1,arr[i]);
  }
  getchar();
}

void sort(int arr[],int low,int mid,int high){
  int i,j,k,l,b[20];
  l=low;
  i=low;
  j=mid+1;

  while((l<=mid)&&(j<=high)){
    if(arr[l]<=arr[j]){
      b[i]=arr[l];
      l++;
    }
    else{
      b[i]=arr[j];
      j++;
    }
    i++;
  }
  if(l>mid){
    for( k = j; k<= high; k++ ){
        b[i] = arr[k];
        i++;
    }
  }
  else{
    for( k=l; k<=mid; k++ ){

      b[i] = arr[k];
      i++;
    }
  }
  for( k = low; k <= high; k++ ){
    arr[k] = b[k];
  }
}
void partition( int arr[],int low,int high){
  int mid, k = 0;
  if( low < high ) {

      mid=( low + high )/2;
      partition( arr, low, mid);
      partition( arr, mid+1, high);
      sort( arr, low, mid, high);
  }

  printf("\n");
  for( k = low; k <= high; k++ )
    printf(" %d", arr[k] );
}


int main( int argc, char *argv[] ){
  int *arr;
  int n, i;

  n = atoi( argv[1] );

  arr = ( int * ) malloc( sizeof( int ) * n );

  for( i = 0; i < n; i++ ){

    arr[i] = rand() % n;
  }
  partition( arr, 0, n-1 );
  display( arr, n );
  getchar();
  return 0;
}

[ArkM]

Regrettably I have no time to study your program in details, but:

Line #17: you declare b[20] array. As far as I know this temporary array must be large enough to contain at least (high-low+1) elements (I don't remember now, may be hight-low). In other words it's too small.

You must allocate this temporary array dynamically then deallocate it just before return.

void sort(...
int* b = malloc(sizeof*b*(high-low+1));
...
free(b);
}

May be it helps...
Good luck!

[Dewey1040]

now i get this error which ive never even seen before

*** glibc detected *** malloc(): memory corruption (fast): 0x09556fd8 ***
59 690 763 926Aborted

[ArkM]

It's the same error: you have memory corruption, that's why you got seg faults and have other troubles...