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

#define MAX_BUF 50 // Size of the buffer to hold intermediate result
#define CUTOFF 18 // Quick sort cutoff

typedef int (*Comparable) ( const void *a, const void *b ); //pointer to function

void low_level_copy(void *target, void *source, unsigned int size){
unsigned int count = 0;
void *from = source;
void *to = target;

if(size < 0)
return;
else if(size == 0)
return;

while(1){

if(count > size)
break;
else if(count == size)
break;

memcpy(to, from, 1);

from = from+1;
to = to+1;
count = count+1;
}
}

int product(int m, int n){
int sum;
int i;
sum = 0;

for(i = 0; i<n; i++){
sum = sum + m;
}

return sum;
}
void jw_insertion_sort ( void *base, int size, int n, Comparable cmp )
{
unsigned char save[MAX_BUF];
unsigned char *cbase = base;
int i, j;

for ( i = 1;; i++ )
{
if( n < 0)
break;
else if( n == 0)
break;

if( i > n)
break;
else if( i == n)
break;

low_level_copy ( save, cbase + product(i, size), size );

for ( j = i;; j-- ){

if(j < 0)
break;
else if(j == 0)
break;
else if(cmp ( (cbase + product( j - 1 , size )), save ) < 0)
break;
else if(cmp ( (cbase + product( j - 1 , size )), save ) == 0)
break;

low_level_copy ( cbase + product( j , size ), cbase + product( j - 1 , size ), size );
}

low_level_copy ( cbase + product( j , size ), save, size );
}

}

void swap_block ( void *a, void *b, int size )
{

if(size < 0)
return;
else if(size == 0)
return;

unsigned char save_block[MAX_BUF];

low_level_copy ( save_block, a, size );
low_level_copy ( a, b, size );
low_level_copy ( b, save_block, size );
}

void jw_quick_sort ( void *base, int size, int low, int high, Comparable cmp )
{
if(high < low)
return;
else if(high == low)
return;

unsigned char save[MAX_BUF];
unsigned char *cbase = base;

int left = low, right = high + 1;
int r;

if ( high - low < CUTOFF )
return;

r = (int) ( ( (double)rand() * ( high - low ) ) / (double)RAND_MAX + low );

swap_block ( cbase + product( low , size ), cbase + product( r , size ), size );

low_level_copy ( save, cbase + product( low , size ), size );

for ( ; ; ) {

while (1){
left = left + 1;

if(left > high)
break;
else if(cmp ( cbase + product( left , size ), save ) > 0)
break;
else if(cmp ( cbase + product( left , size ), save ) == 0)
break;

}

while (1){
right = right - 1;

if(right < 0)
break;
else if(cmp ( cbase + product( right , size ), save ) < 0 )
break;
else if(cmp ( cbase + product( right , size ), save ) == 0 )
break;

}

if ( left > right )
break;

swap_block ( cbase + product( left , size ), cbase + product( right , size ), size );
}

swap_block ( cbase + product( low , size ), cbase + product( right , size ), size );

jw_quick_sort ( base, size, low, right - 1, cmp );
jw_quick_sort ( base, size, right + 1, high, cmp );

}

void jw_sort ( void *base, int size, int n, Comparable cmp )
{
jw_quick_sort ( base, size, 0, n - 1, cmp );
jw_insertion_sort ( base, size, n, cmp );
}

int compare ( const void *a, const void *b ) //improve this function
{
int *aa = (int *)a;
int *bb = (int *)b;
if ( *aa < *bb )
return -1;
else if ( *aa > *bb )
return +1;

return 0;
}
/*****************************************************************************
Do not touch main function
*****************************************************************************/
int main ( void )
{
int a0[10];
int *a1 = malloc ( 1000000 * sizeof ( int ) );
int i, n;
clock_t start;
double jw_time;

for ( i = 0; i < 1000000; i++ )
a1[i] = rand();

start = clock();

jw_sort ( a1, sizeof ( int ), 1000000, compare );

jw_time = ( (double)clock() - start ) / CLOCKS_PER_SEC;

printf ( "Total time consumed in sorting : %f second \n", jw_time );

free ( a1 );

return 0;
}