#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define ZZ 16
#define MEMCPY(XX,YY,SS) {DES=(XX);SRC=(YY);M=(SS); do {*DES++=*SRC++;} while (--M); }

void str_insert(char *keys, int n, int size, int (*compare) ())
{
        register int i,j,M;
        char    *x,*DES,*SRC;

        x = (char *) malloc(size*sizeof(char));
        for(j=1;j<n;j++) {
                MEMCPY(x,&keys[j*size],size);
                i=j-1;
                while ( (i>=0) && ( compare(&keys[i*size],x)>0) ) {
                        MEMCPY(&keys[(i+1)*size],&keys[i*size],size);
                        i--;
                }
                MEMCPY(&keys[(i+1)*size],x,size);
        }
}


void quick_1_sort(char *keys, int n, int size, int (*compare) (),int l,int r)
{
        register int i,j,M;
        char    *x,*y,*DES,*SRC;

        i=l;j=r;
        x = (char *) malloc(size*sizeof(char));
        y = (char *) malloc(size*sizeof(char));
        MEMCPY(x,&keys[((l+r)/2)*size],size);

do
{
        while (compare(&keys[i*size],x) < 0) ++i;
        while (compare(x,&keys[j*size]) < 0) --j;
        if (i <= j ) {
                MEMCPY(y,&keys[i*size],size);
                MEMCPY(&keys[i*size],&keys[j*size],size);
                MEMCPY(&keys[j*size],y,size);
                ++i;--j;
        }
} while (i <= j);

        if (l < j) {
                if ((j-l) < ZZ)
                        str_insert(&keys[l*size],(j-l+1),size,compare);
                else
                        quick_1_sort(keys,n,size,compare,l,j);
        }
        if (i < r) {
                if ((r-i) < ZZ)
                        str_insert(&keys[i*size],(r-i+1),size,compare);
                else
                        quick_1_sort(keys,n,size,compare,i,r);
        }

}

void g67(char *keys, int n, int size, int (*compare) (const void*,const void*))
{
                quick_1_sort(keys,n,size,compare,0,n-1);
}

