#include <stdio.h>

#define	BYTE(x)		*((unsigned char *)(x))
#define	WORD(x)		*((unsigned short int *)(x))
#define	DWORD(x)	*((unsigned long int *)(x))
#define POINT(x)	*((char **)(x))

#define	SGN(x)		( (x>0)? 1: ((x<0)? -1: x) )

#define SORT_BUBBLE	1
#define SORT_SHELL	2

#define	SORT_CHAR	1
#define	SORT_SHORT	2
#define	SORT_LONG	3
#define	SORT_STR	4

#define	CHAR_SIZE	sizeof(char)
#define	SHORT_SIZE	sizeof(short)
#define	LONG_SIZE	sizeof(long)
#define	POINT_SIZE	sizeof(char *)

#define	NOEXCHANGE	0
#define	EXCHANGE	1

static int	type;
static int	*lank;
static char	*base;
static int	element;

static int	compare( int offset1, int offset2 );
static void	shellswap( int length, int offset );
static void	shellsort();
static void	bubblesort();

static int compare( int offset1, int offset2 )
{
	long int	i,j;

	switch( type )
	{
		case SORT_CHAR:
			i = BYTE( base + CHAR_SIZE * offset1 )
				- BYTE( base + CHAR_SIZE * offset2 );
			break;
		case SORT_SHORT:
			i = WORD( base + SHORT_SIZE * offset1 )
				- WORD( base + SHORT_SIZE * offset2 );
			break;
		case SORT_LONG:
			i = DWORD( base + LONG_SIZE * offset1 )
				- DWORD( base + LONG_SIZE * offset2 );
			break;
		case SORT_STR:
			j = 0;
			while(1)
			{
				i = BYTE( POINT( base + POINT_SIZE * offset1 ) + CHAR_SIZE * j )
					- BYTE( POINT( base + POINT_SIZE * offset2 ) + CHAR_SIZE * j );
				if( i )
					break;
				if( BYTE( POINT( base + POINT_SIZE * offset1 ) + CHAR_SIZE * j ) == 0 )
					break;
				++ j;
			}
			break;
	}

	return SGN(i);
}

static void shellswap( int length, int offset )
{
	if( compare( lank[offset], lank[offset+length] ) > 0 )
	{
		int		i;
		i = lank[offset];
		lank[offset] = lank[offset+length];
		lank[offset+length] = i;
		if( offset < length )
			return;
		shellswap( length, offset-length );
	}
	return;
}

static void shellsort()
{
	int		i,length;

	length = element;
	while( length>=1 )
	{
		length /= 2;
		for( i=0; i+length<element; i++ )
			shellswap( length, i );
	}

	return;
}

static void bubblesort()
{
	int		i,j,k;

	for( i=0; i<element; i++ )
		for( j=i+1; j<element; j++ )
			if( compare( lank[i], lank[j] ) > 0 )
			{
				k = lank[i];
				lank[i] = lank[j];
				lank[j] = k;
			}

	return;
}

void	sort( int sorttype, int argtype, void *data, int n, int *retlank )
{
	int		i;

	type = argtype;
	base = data;
	element = n;
	lank = retlank;

	for( i=0; i<element; i++ )
		*(lank+i) = i;

	switch( sorttype )
	{
		case SORT_SHELL:
			shellsort();
			break;
		case SORT_BUBBLE:
			bubblesort();
			break;
	}

	return;
}