In-place merge sort

in_place_merge_sort.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <sys/time.h>

void print(int* a, int n){
    int i=0;
    printf("[");
    for(i=0;i<n;i++){
        if(i>0) 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(j<n){
        if(rand()%2){
            *(sample_data+j) = i;
            j++;
        }
        if(rand()%100>0){
            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<n;i++){
        d = rand()%n;
        tmp = *(random_data+d);
        *(random_data+d) = *(random_data+s);
        *(random_data+s) = tmp;
        s = d;
    }
    return random_data;
}

int assert(int* a, int* b, int n){
    if(memcmp(a,b,n)){
        return 0;
    }else{
        return 1;
    }
}

int find_last_less( int* p, int n, int key )
{
    // if the first element of given list is NOT smaller than key
    if ( !(p[0]<key) ){
        return -1;
    }

    // if the last element of given list is smaller than key
    if ( p[n-1]<key ){
        return n-1;
    }

    // binary search to find the index of an element
    // which devides the list by the key
    int less=0;
    int ge=n-1;
    while( less+1<ge ){
        int mid = less + (ge-less)/2;
        if ( p[ mid ]<key ){
            less = mid;
        } else {
            ge = mid;
        }
    }

    // The last index which is less than key
    // Note that less must be less than key
    return less;
}

// Least Common Multiple
// = Greatest Common Divisor (GCD)
int gcd( int a, int b )
{
    for(;;){
        if ( b==0 ){
            return a;
        }
        int c = a%b;
        a=b;
        b=c;
    }
}

void rot_left( int * p, int size, int rot )
{

    //
    // * Example to explain rotation * //
    //
    // original p = { 0,2,4,6,8, 1,2,3,4,5 }
    // Just suppose key = 5
    // rot_left p = { 6,8, 1,2,3,4, (5) }
    //
    // size = 6 ( p = { < 6,8, 1,2,3,4 > ,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<g ; ++start ){
        int i=( start + rot )%size;
        int head = p[i];
        while( i != start ){
            int next = ( i+rot )%size;
            p[i] = p[ next ];
            i=next;
        }
        p[start]=head;
    }
}

void merge( int * p, int left, int right )
{
    // left is the number of the left list
    // right is the number of the right list
    if ( left==0 || right==0 ){
        return;
    }
    // p[left-1] is the laste element of left
    // [[left]   is the first element of right
    if ( p[ left-1 ]<=p[ left ] ){
        // Right list is already bigger than or equal to left list.
        // No need to merge anymore.
        return;
    }
    if ( left==1 && right ==1 ){
        if ( p[1]<p[0] ){
            int t;
            t=p[1]; p[1]=p[0]; p[0]=t;
        }
        return;
    }

    // Take the middle of list as a key
    int key = left<right ? p[ left + (right+1)/2 ] : p[ (left+1)/2 ];

    // If the key is smaller than right and left list, change the key
    if ( key <= p[ left ]  &&  key <= p[0] ){
        // Take the last bigger element of right or left list
        key = p[left-1]<p[left+right-1] ? p[left+right-1] : p[left-1];
    }

    // find the index which points to the biggest one less than key
    int mL = find_last_less( p, left, key );
    int mR = find_last_less( p+left, right, key );

    // This is the first index which points to the smallest one larger than key
    int mLL = mL + 1;
    int mRL = mR + 1;

    // The number of values which is larger than key in each list
    int mLGE = left-mLL;
    int mRGE = right - mRL;

    // e.g.
    // p = { 0,2,4,6,8, 1,2,3,4,5 }
    //   - left = { 0,2,4,6,8 }
    //   - right= { 1,2,3,4,5 }
    // key = 5
    //
    // mL = 2 (index points to 4 in left)
    // mLL = 3 (mL + 1)
    // mLGE = 2 (The size of left(5) - mLL)
    //
    // mR = 3 (index points to 4 in right)
    // mRL = 4
    // mRGE = 1 (The size of right(5) - mRL)
    
    // 1st: Pointer points to the first argument larger than the key
    //      in the left list
    // 2nd: The number of values larger than the key in the left list
    //    + the first index larger than the key in the right list
    // 3rd: The number of values larger than the key in the left list
    rot_left( p+mLL, mLGE + mRL, mLGE );
    
    // After rotation, p+mLL is
    // { < 1,2, 3,4,6,8 > ,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]<data[0]){
        int t=data[0];
        data[0]=data[1];
        data[1]=t;
        }
        return;
    }


    int half = n/2;

    in_place_merge_sort(data,half);
    in_place_merge_sort(data+half,n-half);

    merge(data,half,n-half);


}

void do_assert(int* sample_data, int* sorted_data, int n){
    if(assert(sample_data,sorted_data,n)){
        printf("Sorted check OK.\n");
    }else{
        printf("Sorted check NG.\n");
        print(sample_data,n>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;
}

$ 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.