Instantly share code, notes, and snippets.

# nishidy/in_place_merge_sort.c Last active Dec 16, 2016

In-place merge sort
 #include #include #include #include #include void print(int* a, int n){ int i=0; printf("["); for(i=0;i0) printf(","); printf("%d",*(a+i)); } printf("]\n"); } double print_time(struct timeval *s, struct timeval *e){ int si = (s->tv_sec%1000000)*1000+s->tv_usec/1000; int ei = (e->tv_sec%1000000)*1000+e->tv_usec/1000; return (double)(ei-si)/1000.0; } int* sample(int n){ int* sample_data = (int*)malloc(sizeof(int)*n); int i=0; int j=0; while(j0){ i++; } } return sample_data; } int* shuffle(int* data, int n, int* random_data){ memcpy(random_data,data,sizeof(int)*n); int s = rand()%n; int i, d, tmp; for(i=0;i ,5 } // rot = 2 ( p = { < 6,8 >, 1,2,3,4,5 } // // then, gcd is 2 and rotate as follows // { < 6,8, 1,2,3,4 > ,5 } <= rot_left p // { < 1,8, 3,2,6,4 > ,5 } // { < 1,2, 3,4,6,8 > ,5 } // int g = gcd( size, rot ); for( int start=0 ; start ,5 } // Then p is // { 0,2,4, 1,2, 3,4,6,8 ,5 } // // Divide this list for four lists as follows // left is { 0,2,4 }, right { 1,2 } merge( p, mLL, mRL ); // left is { 3,4,6,8 }, right { 5 } merge( p+mLL+mRL, mLGE, mRGE ); } void in_place_merge_sort(int *data, int n){ if(n<=1) return; if(n==2){ if(data[1]100?100:n); print(sorted_data,n>100?100:n); } } int main(int argc, char *argv[]){ if(argc<2){ printf("Give # of samples.\n"); exit(1); } int n = atoi(argv[1]); int *sample_data; struct timeval s, e; //srand((unsigned) time(NULL)); srand(100); sample_data = sample(n); int* random_data = (int*)malloc(sizeof(int)*n); shuffle(sample_data,n,random_data); gettimeofday(&s,NULL); in_place_merge_sort(random_data,n); gettimeofday(&e,NULL); printf("In place merge sort : %.2lf sec.\n",print_time(&s,&e)); do_assert(sample_data,random_data,n); return 0; }
Owner

### nishidy commented Dec 10, 2016 • edited Edited 1 time nishidy edited Dec 16, 2016 (most recent)

 ``````\$ gcc -W -O3 in_place_merge_sort.c -o in_place_merge_sort \$ ./in_place_merge_sort 100000000 In place merge sort : 178.77 sec. Sorted check OK. ``````