Shortcut for chapter specific information

Wednesday, May 4, 2011

Merge sort 5(C)

Merge sort 5 : Good


My current version without extra insertion sort:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 20
void merge(int a[],int w[],int p, int m, int r)
{
  int i,j,k;
  i=p;
  j=m+1;
  k=p;
  while(i<=m&&j<=r)
    w[k++]=(a[i]<a[j])?a[i++]:a[j++];
  while(i<=m)
    w[k++]=a[i++];
  while(j<=r)
    w[k++]=a[j++];
}
void merge_sort(int a[],int w[],int p,int r)
{
  if(p<r){
    int m = (p+r)/2;
    merge_sort(a,w,p,m);
    merge_sort(a,w,m+1,r);
    merge(a,w,p,m,r);
    memmove(&a[p],&w[p],(r-p+1)*sizeof(int)/sizeof(char));
  }
}
int main(int c, char* v[])
{
  int A[N]={20,1,3,4,-1,5,7,9,-10,-20,6,9,10,0,9,100,-100,0,-11,77};
  int W[N];
  int i;
  merge_sort(A,W,0,N-1);
  for(i=0;i<N;i++)
    printf("%d ",A[i]);
  printf("\n");
  return 0;
}




Awesome! My first hand-crafted NLogN search!
Next:
-Put this into my practice from now on. 
-It's time to finish 2.3-2
-It would be fun to sort 1 M number and time.

No comments:

Post a Comment