ソート関数プログラム

［ 簡単な説明 ］

各種のソート用関数、昇順⇔降順のデータ入替え関数、および文字列配列のダイナミックアロケーション用関数を定義しています。

各ソート用関数は、配列名とサイズを引数として与えると、昇順にソーティングします。
但し、逆写像ソート、および分布数えソートは、データの分布範囲（ max、min ）も引数として与える必要があります。
また、ラディックスソートは文字列長を引数として加えます。
間接ソート系の関数は、引数に int 型配列名を加えて指定すると、データ配列要素のソーティング後の並び順が指定した int 型配列に入れて返されます。

昇順⇔降順のデータ入替え関数は、配列名とサイズを引数として与えると、その配列要素の順番を入替えます。
無条件に入替えますので、同一配列およびサイズで２回続けて呼び出すと、元の配列に戻ります。

文字列配列のダイナミックアロケーション用関数は、（'\0' を除く）要素数と最大文字列長を与えるとその配列のポインタを返します。

ソート用関数
クイックソート qsort_i( )
qsort_d( )
qsort_c( )		 　 逆写像ソート mapsort( )
バブルソート bsort_i( )
bsort_d( )
bsort_c( )		 　 分布数えソート distsort_i( )
distsort_d( )
挿入ソート inssort_i( )
inssort_d( )
inssort_c( )		 　 ラディックスソート radsort( )
選択ソート ssort_i( )
ssort_d( )
ssort_c( )		 　 間接クイックソート iqsort_i( )
iqsort_d( )
iqsort_c( )
マージソート msort_i( )
msort_d( )
msort_c( )		 　 間接分布数えソート idistsort( )
ヒープソート hsort_i( )
hsort_d( )
hsort_c( )		 　 　 　


昇順⇔降順データ入換え用関数
void inv_i( )
void inv_d( )
void inv_c( )


uchar 型配列のダイナミックアロケーション用関数
uchar **salloc( )
プログラム・ソース（"sort1.c"） 　　　　　　　　　　top （トップに戻る） 
/*		sort1.c			sort subroutine source file		*/
/*#define		DEBUG
#include <stdio.h>
#include <stdlib.h>
#include "sort.h"

uchar **salloc(int n, int len)
{
	uchar **s, **p;
	uchar *c;
	static int i;

	s = (uchar **)malloc(sizeof(uchar *) * n);
	if(s == NULL)
	{
		fprintf(stderr, "Error : out of memory  in salloc()\n");
		return NULL;
	}

	for(i = 0, p = s; i < n; i++)
	{
		c = (uchar *)malloc(sizeof(uchar) * (len + 1));
		if(c == NULL)
		{
			fprintf(stderr, "Error : out of memory  in salloc()\n");
			return NULL;
		}
		*p++ = c;
	}
	return s;
}

int strcomp(uchar *a, uchar *b)
{
	uchar *p, *q;

	p = a;
	q = b;
	while(*p)
	{
		if(*p > *q)	return 1;
		if(*p++ < *q++)	return -1;
	}
	if(*q)	return -1;
	return 0;
}

void qsort_i(int a[], int n)
{
	if(n <= 1)
	{
		fprintf(stderr, "Error : n <= 1  in qsort_i()\n");
		return;
	}
	subquick_i(a, a + n - 1);
}

void subquick_i(int *first, int *last)
{
	int w;
	int *i, *j, *p;
	int x, t;

	if((w = last - first) < 11)	inssort_i(first, w + 1);
	else
	{
		x = *(first + (int)((last - first) / 2));
		i = first;
		j = last;
		do
		{
			while(x > *i)	i++;
			while(*j > x)	j--;
			if(i > j)	break;
			t = *i;
			*i++ = *j;
			*j-- = t;
		} while(i <= j);
		if(i - 1 > first)	subquick_i(first, i - 1);
		if(j + 1 < last)	subquick_i(j + 1, last);
	}
}

void qsort_d(double a[], int n)
{
	if(n <= 1)
	{
		fprintf(stderr, "Error : n <= 1  in qsort_d()\n");
		return;
	}
	subquick_d(a, a + n - 1);
}

void subquick_d(double *first, double *last)
{
	int w;
	double *i, *j, *p;
	double x, t;

	if((w = last - first) < 11)	inssort_d(first, w + 1);
	else
	{
		x = *(first + (int)((last - first) / 2));
		i = first;
		j = last;
		do
		{
			while(x > *i)	i++;
			while(*j > x)	j--;
			if(i > j)	break;
			t = *i;
			*i++ = *j;
			*j-- = t;
		} while(i <= j);
		if(i - 1 > first)	subquick_d(first, i - 1);
		if(j + 1 < last)	subquick_d(j + 1, last);
	}
}

void qsort_c(uchar *a[], int n)
{
	uchar **i, **j, **l, **r;
	uchar **st1[32], **st2[32], ***s1, ***s2;
	uchar *x, *w;

	if(n <= 1)
	{
		fprintf(stderr, "Error : n <= 1  in qsort_c()\n");
		return;
	}

	s1 = st1;
	s2 = st2;
	*s1 = a;
	*s2 = a + n - 1;
	do
	{
		l = *s1--;
		r = *s2--;
		if(r - l < 11)	inssort_c(l, r - l + 1);
		else
		{
			do
			{
				i = l;
				j = r;
				x = *(l + (int)((r - l) / 2));
				do
				{
					while(strcomp(x, *i) > 0)	i++;
					while(strcomp(*j, x) > 0)	j--;
					if(i > j)	break;
					w = *i;
					*i++ = *j;
					*j-- = w;
				} while(i <= j);
				if(j - l < r - i)
				{
					if(i < r)
					{
						*(++s1) = i;
						*(++s2) = r;
					}
					r = j;
				}
				else
				{
					if(l < j)
					{
						*(++s1) = l;
						*(++s2) = j;
					}
					l = i;
				}
			} while(l < r);
		}
	}while (s1 >= st1);
	return;
}

void bsort_i(int a[], int n)
{
	int x;
	int h, i, j;

	if(n <= 1)
	{
		fprintf(stderr, "Error : n <= 1  in bsort_i()\n");
		return;
	}

	h = n - 1;
	do
	{
		j = -1;
		for(i = 1; i <= h; i++)
		{
			if(a[i - 1] > a[i])
			{
				j = i - 1;
				x = a[j];
				a[j] = a[i];
				a[i] = x;
			}
		}
		h = j;
	} while(h >= 0);
}

void bsort_d(double a[], int n)
{
	double x;
	int h, i, j;

	if(n <= 1)
	{
		fprintf(stderr, "Error : n <= 1  in bsort_d()\n");
		return;
	}

	h = n - 1;
	do
	{
		j = -1;
		for(i = 1; i <= h; i++)
		{
			if(a[i - 1] > a[i])
			{
				j = i - 1;
				x = a[j];
				a[j] = a[i];
				a[i] = x;
			}
		}
		h = j;
	} while(h >= 0);
}

void bsort_c(uchar *a[], int n)
{
	uchar *x;
	int h, i, j;

	if(n <= 1)
	{
		fprintf(stderr, "Error : n <= 1  in bsort_c()\n");
		return;
	}

	h = n - 1;
	do
	{
		j = -1;
		for(i = 1; i <= h; i++)
		{
			if(strcomp(*(a + i - 1), *(a + i)) > 0)
			{
				j = i - 1;
				x = a[j];
				a[j] = a[i];
				a[i] = x;
			}
		}
		h = j;
	} while(h >= 0);
}

void inssort_i(int a[], int n)
{
	int x;
	int i, j;

	if(n <= 1)
	{
		fprintf(stderr, "Error : n <= 1  in inssort_i()\n");
		return;
	}
	for(i = 1; i < n; i++)
	{
		x = a[i];
		j = i - 1;
		while(j >= 0 && a[j] > x)
		{
			a[j + 1] = a[j];
			j--;
		}
		a[j + 1] = x;
	}
}

void inssort_d(double a[], int n)
{
	double x;
	int i, j;

	if(n <= 1)
	{
		fprintf(stderr, "Error : n <= 1  in inssort_d()\n");
		return;
	}
	for(i = 1; i < n; i++)
	{
		x = a[i];
		j = i - 1;
		while(j >= 0 && a[j] > x)
		{
			a[j + 1] = a[j];
			j--;
		}
		a[j + 1] = x;
	}
}

void inssort_c(uchar *a[], int n)
{
	uchar *x;
	int i, j;

	if(n <= 1)
	{
		fprintf(stderr, "Error : n <= 1  in inssort_c()\n");
		return;
	}
	for(i = 1; i < n; i++)
	{
		x = a[i];
		j = i - 1;
		while(j >= 0 && strcomp(a[j], x) > 0)
		{
			a[j + 1] = a[j];
			j--;
		}
		a[j + 1] = x;
	}
}

void ssort_i(int a[], int n)
{
	int min;
	int *ak, *alast, *p, *q;

	if(n <= 1)
	{
		fprintf(stderr, "Error : n <= 1  in ssort_i()\n");
		return;
	}
	alast = (p = a) + n - 1;
	while(p < alast)
	{
		min = *(ak = q = p);
		while(++q <= alast)	if(*q < min)	min = *(ak = q);
		min = *ak;
		*ak = *p;
		*p++ = min;
	}
}

void ssort_d(double a[], int n)
{
	double min;
	double *ak, *alast, *p, *q;

	if(n <= 1)
	{
		fprintf(stderr, "Error : n <= 1  in ssort_d()\n");
		return;
	}
	alast = (p = a) + n - 1;
	while(p < alast)
	{
		min = *(ak = q = p);
		while(++q <= alast)	if(*q < min)	min = *(ak = q);
		min = *ak;
		*ak = *p;
		*p++ = min;
	}
}

void ssort_c(uchar *a[], int n)
{
	uchar *min;
	uchar **ak, **alast, **p, **q;

	if(n <= 1)
	{
		fprintf(stderr, "Error : n <= 1  in ssort_c()\n");
		return;
	}
	alast = (p = a) + n - 1;
	while(p < alast)
	{
		min = *(ak = q = p);
		while(++q <= alast)	if(strcomp(*q, min) < 0)	min = *(ak = q);
		min = *ak;
		*ak = *p;
		*p++ = min;
	}
}

void msort_i(int a[], int n)
{
	int *work;

	if(n <= 1)
	{
		fprintf(stderr, "Error : n <= 1  in msort_i()\n");
		return;
	}

	work = (int *)malloc(sizeof(int) * (int)(n / 2 + 1));
	if(work == NULL)
	{
		fprintf(stderr, "out of memory  in msort_i()\n");
		return;
	}
	submerge_i(work, a, a + n - 1);
	free((uchar *)work);
}

void submerge_i(int *work, int *afirst, int *alast)
{
	int n;
	int *ak, *ap, *amiddle, *w, *wp;

	if((n = alast - afirst) < 11)	inssort_i(afirst, n + 1);
	else
	{
		amiddle = afirst + (int)(n / 2);
		submerge_i(work, afirst, amiddle);
		submerge_i(work, amiddle + 1, alast);
		ak = ap = afirst;
		w = wp = work;
		while(ap <= amiddle)	*w++ = *ap++;
		while(ap <= alast && wp < w)
			if(*wp <= *ap)	*ak++ = *wp++;
			else			*ak++ = *ap++;
		while(wp < w)	*ak++ = *wp++;
	}
}

void msort_d(double a[], int n)
{
	double *work;

	if(n <= 1)
	{
		fprintf(stderr, "Error : n <= 1  in msort_d()\n");
		return;
	}

	work = (double *)malloc(sizeof(double) * (int)(n / 2 + 1));
	if(work == NULL)
	{
		fprintf(stderr, "out of memory  in msort_d()\n");
		return;
	}
	submerge_d(work, a, a + n - 1);
	free((uchar *)work);
}

void submerge_d(double *work, double *afirst, double *alast)
{
	int n;
	double *ak, *ap, *amiddle, *w, *wp;

	if((n = alast - afirst) < 11)	inssort_d(afirst, n + 1);
	else
	{
		amiddle = afirst + (int)(n / 2);
		submerge_d(work, afirst, amiddle);
		submerge_d(work, amiddle + 1, alast);
		ak = ap = afirst;
		w = wp = work;
		while(ap <= amiddle)	*w++ = *ap++;
		while(ap <= alast && wp < w)
			if(*wp <= *ap)	*ak++ = *wp++;
			else			*ak++ = *ap++;
		while(wp < w)	*ak++ = *wp++;
	}
}

void msort_c(uchar *a[], int n, int len)
{
	uchar **work;
	if(n <= 1)
	{
		fprintf(stderr, "Error : n <= 1  in msort_c()\n");
		return;
	}

	work = salloc((int)(n / 2 + 1), len);
	if(work == NULL)
	{
		fprintf(stderr, "out of memory  in msort_c()\n");
		return;
	}
	submerge_c(work, a, a + n - 1);
	free((uchar *)work);
}

void submerge_c(uchar **work, uchar **afirst, uchar **alast)
{
	int n;
	uchar **ak, **ap, **amiddle, **w, **wp;

	if((n = alast - afirst) < 11)	inssort_c(afirst, n + 1);
	else
	{
		amiddle = afirst + (int)(n / 2);
		submerge_c(work, afirst, amiddle);
		submerge_c(work, amiddle + 1, alast);
		ak = ap = afirst;
		w = wp = work;
		while(ap <= amiddle)	*w++ = *ap++;
		while(ap <= alast && wp < w)
			if(strcomp(*wp, *ap) <= 0)	*ak++ = *wp++;
			else						*ak++ = *ap++;
		while(wp < w)	*ak++ = *wp++;
	}
}

void hsort_i(int a[], int n)
{
	int j, k;
	int *alast, *pi, *pj, x;

	if(n <= 1)
	{
		fprintf(stderr, "Error : n <= 1  in hsort_i()\n");
		return;
	}

	alast = a + n - 1;
	for(k = n / 2; k >= 1; k--)
	{
		x = *(pi = a + (j = k) - 1);
		while((j *= 2) < n)
		{
			pj = a + j - 1;
			if(pj < alast && *pj < *(pj + 1))	pj++;
			j = pj - a + 1;
			if(x >= *pj)	break;
			*pi = *pj;
			pi = pj;
		}
		*pi = x;
	}
	while(n > 0)
	{
		x = *alast;
		*alast = *a;
		alast = (pi = a) + (--n) - (j = 1);
		while((j *= 2) <= n)
		{
			pj = a + j - 1;
			if(pj < alast && *pj < *(pj + 1))	pj++;
			j = pj - a + 1;
			if(x >= *pj)	break;
			*pi = *pj;
			pi = pj;
		}
		*pi = x;
	}
}

void hsort_d(double a[], int n)
{
	int j, k;
	double *alast, *pi, *pj, x;

	if(n <= 1)
	{
		fprintf(stderr, "Error : n <= 1  in hsort_d()\n");
		return;
	}

	alast = a + n - 1;
	for(k = n / 2; k >= 1; k--)
	{
		x = *(pi = a + (j = k) - 1);
		while((j *= 2) < n)
		{
			pj = a + j - 1;
			if(pj < alast && *pj < *(pj + 1))	pj++;
			j = pj - a + 1;
			if(x >= *pj)	break;
			*pi = *pj;
			pi = pj;
		}
		*pi = x;
	}
	while(n > 0)
	{
		x = *alast;
		*alast = *a;
		alast = (pi = a) + (--n) - (j = 1);
		while((j *= 2) <= n)
		{
			pj = a + j - 1;
			if(pj < alast && *pj < *(pj + 1))	pj++;
			j = pj - a + 1;
			if(x >= *pj)	break;
			*pi = *pj;
			pi = pj;
		}
		*pi = x;
	}
}

void hsort_c(uchar *a[], int n)
{
	int j, k;
	uchar **alast, **pi, **pj, *x;

	if(n <= 1)
	{
		fprintf(stderr, "Error : n <= 1  in hsort_c()\n");
		return;
	}

	alast = a + n - 1;
	for(k = n / 2; k >= 1; k--)
	{
		x = *(pi = a + (j = k) - 1);
		while((j *= 2) < n)
		{
			pj = a + j - 1;
			if(pj < alast && strcomp(*pj, *(pj + 1)) < 0)	pj++;
			j = pj - a + 1;
			if(strcomp(x, *pj) >= 0)	break;
			*pi = *pj;
			pi = pj;
		}
		*pi = x;
	}
	while(n > 0)
	{
		x = *alast;
		*alast = *a;
		alast = (pi = a) + (--n) - (j = 1);
		while((j *= 2) <= n)
		{
			pj = a + j - 1;
			if(pj < alast && strcomp(*pj, *(pj + 1)) < 0)	pj++;
			j = pj - a + 1;
			if(strcomp(x, *pj) >= 0)	break;
			*pi = *pj;
			pi = pj;
		}
		*pi = x;
	}
}

void mapsort(int a[], int n, int max, int min)
{
	int i, j;
	int *index, *lindex, *next, *p, *q, *r, x;

	if(n <= 1)
	{
		fprintf(stderr, "Error : n <= 1  in mapsort()\n");
		return;
	}

	index = (int *)malloc(sizeof(int) * (max - min + 1));
	next = (int *)malloc(sizeof(int) * n);
	if(index == NULL || next == NULL)
	{
		fprintf(stderr, "Error : out of memory  in mapsort()\n");
		return;
	}

	lindex = p = index + max - min;
	while(p >= index)	*p-- = -1;
	p = a + (i = n - 1);
	q = next + i;
	while(p >= a)
	{
		*q-- = *(r = index + (x = *p-- - min));
		*r = i--;
	}
	for(x = min, p = a, q = index; q <= lindex; x++)
	{
		i = *q++;
		while(i >= 0)
		{
			*p++ = x;
			i = *(next + i);
		}
	}

	free((uchar *)next);
	free((uchar *)index);
}

void distsort_i(int a[], int n, int max, int min)
{
	int m;
	int *b, *count, *p, *pp, *q;
	int *clast, *r;

	if(n <= 1 || max <= min)
	{
		fprintf(stderr, "Error : illegal data input  in distsort_i()\n");
		if(n <= 1)		fprintf(stderr, "     n=%d (n > 2)\n", n);
		if(max <= min)
			fprintf(stderr, "     max=%d, min=%d (max > min)\n", max, min);
		return;
	}

	b = (int *)malloc(sizeof(int) * n);
	count = (int *)malloc(sizeof(int) * ((m = max - min) + 1));
	if(b == NULL || count == NULL)
	{
		fprintf(stderr, "Error : out of memory  in distsort_i()\n");
		return;
	}

	clast = r = count + m;
	while(r >= count)	*r-- = 0;
	p = pp = b + n - 1;
	q = a + n - 1;
	while(q >= a)	(*(count + (*p-- = *q-- - min)))++;
	r = count;
	while(++r <= clast)	*r += *(r - 1);
	while(pp >= b)	*(a + --*(count + *pp)) = *pp-- + min;

	free((uchar *)b);
	free((uchar *)count);
}

void distsort_d(double a[], int n, double max, double min)
{
	double *dp, *dq, *work, ratio;
	int *b, *jun, *p, i, m;

	if(n <= 1 || max <= min)
	{
		fprintf(stderr, "Error : illegal data input  in distsort_d()\n");
		if(n <= 1)		fprintf(stderr, "     n=%d (n > 2)\n", n);
		if(max <= min)
			fprintf(stderr, "     max=%d, min=%d (max > min)\n", max, min);
		return;
	}

	b = (int *)malloc(sizeof(int) * n);
	jun = (int *)malloc(sizeof(int) * n);
	work = (double *)malloc(sizeof(double) * n);
	if(b == NULL || jun == NULL || work == NULL)
	{
		fprintf(stderr, "Error : out of memory  in distsort_d()\n");
		return;
	}
	m = n / 2;
	ratio = (double)m / (max - min);
	for(i = 0, dp = a, dq = work, p = b; i < n; i++)
		*p++ = (int)(((*dq++ = *dp++) - min) * ratio);
	idistsort(b, n, m, 0, jun);
	for(i = 0, dp = a, p = jun; i < n; i++)	*dp++ = *(work + *p++);
	inssort_d(a, n);

	free((uchar *)work);
	free((uchar *)jun);
	free((uchar *)b);
}

void radsort(uchar *a[], int n, int len)
{
	int j;
	int *count, *clast, *p, **index, **ilast, **pp;
	uchar **alast, **pi, **pw, **wlast, **work;

	if(n <= 1)
	{
		fprintf(stderr, "Error : n <= 1  in radsort()\n");
		return;
	}

	work = salloc(n, len);
	count = (int *)malloc(sizeof(int) * 256);
	index = (int **)malloc(sizeof(int *) * n);
	if(work == NULL || count == NULL || index == NULL)
	{
		fprintf(stderr, "Error : out of memory  in radsort()\n");
		return;
	}

	clast = count + 256;
	ilast = index + n - 1;
	alast = a + n;
	wlast = work + n - 1;
	for(j = len - 1, p = clast; j >= 0; j--)
	{
		while(--p >= count) *p = 0;
		pi = alast;
		pp = ilast;
		pw = wlast;
		while(--pi >= a)	(*(*pp-- = count + *((*pw-- = *pi) + j)))++;
		p++;
		while(++p < clast)	*p += *(p - 1);
		pp = ilast;
		pw = wlast;
		while(pw >= work)	*(a + --*(*pp--)) = *pw--;
	}

	free((uchar *)index);
	free((uchar *)count);
	free((uchar *)work);
}

void inv_i(int a[], int n)
{
	int *p, *q, w;

	q = (p = a) + n - 1;
	while(p < q)
	{
		w = *p;
		*p++ = *q;
		*q-- = w;
	}
}

void inv_d(double a[], int n)
{
	double *p, *q, w;

	q = (p = a) + n - 1;
	while(p < q)
	{
		w = *p;
		*p++ = *q;
		*q-- = w;
	}
}

void inv_c(uchar *a[], int n)
{
	uchar **p, **q, *w;

	q = (p = a) + n - 1;
	while(p < q)
	{
		w = *p;
		*p++ = *q;
		*q-- = w;
	}
}

void iqsort_i(int a[], int n, int jun[])
{
	int *i, *j, *l, *r;
	int *st1[32], *st2[32], **s1, **s2;
	int x, w;

	if(n <= 1)
	{
		fprintf(stderr, "Error : n <= 1  in iqsort_i()\n");
		return;
	}
	for(w = 0, r = jun; w < n; )	*r++ = w++;

	s1 = st1;
	s2 = st2;
	*s1 = jun;
	*s2 = jun + n - 1;
	do
	{
		l = *s1--;
		r = *s2--;
		do
		{
			i = l;
			j = r;
			x = *(a + *(l + ((int)(r - l) / 2)));
			do
			{
				while(x > *(a + *i))	i++;
				while(*(a + *j) > x)	j--;
				if(i > j)	break;
				w = *i;
				*i++ = *j;
				*j-- = w;
			} while(i <= j);
			if(j - l < r - i)
			{
				if(i < r)
				{
					*(++s1) = i;
					*(++s2) = r;
				}
				r = j;
			}
			else
			{
				if(l < j)
				{
					*(++s1) = l;
					*(++s2) = j;
				}
				l = i;
			}
		} while(l < r);
	}while (s1 >= st1);
	return;
}

void iqsort_d(double a[], int n, int jun[])
{
	int *i, *j, *l, *r, k;
	int *st1[32], *st2[32], **s1, **s2;
	double x, w;

	if(n <= 1)
	{
		fprintf(stderr, "Error : n <= 1  in iqsort_d()\n");
		return;
	}
	for(k = 0, r = jun; k < n; )	*r++ = k++;

	s1 = st1;
	s2 = st2;
	*s1 = jun;
	*s2 = jun + n - 1;
	do
	{
		l = *s1--;
		r = *s2--;
		do
		{
			i = l;
			j = r;
			x = *(a + *(l + ((int)(r - l) / 2)));
			do
			{
				while(x > *(a + *i))	i++;
				while(*(a + *j) > x)	j--;
				if(i > j)	break;
				w = *i;
				*i++ = *j;
				*j-- = w;
			} while(i <= j);
			if(j - l < r - i)
			{
				if(i < r)
				{
					*(++s1) = i;
					*(++s2) = r;
				}
				r = j;
			}
			else
			{
				if(l < j)
				{
					*(++s1) = l;
					*(++s2) = j;
				}
				l = i;
			}
		} while(l < r);
	}while (s1 >= st1);
	return;
}

void iqsort_c(uchar *a[], int n, int jun[])
{
	int *i, *j, *l, *r, w;
	int *st1[32], *st2[32], **s1, **s2;
	uchar *x;

	if(n <= 1)
	{
		fprintf(stderr, "Error : n <= 1  in iqsort_d()\n");
		return;
	}
	for(w = 0, r = jun; w < n; )	*r++ = w++;

	s1 = st1;
	s2 = st2;
	*s1 = jun;
	*s2 = jun + n - 1;
	do
	{
		l = *s1--;
		r = *s2--;
		do
		{
			i = l;
			j = r;
			x = *(a + *(l + ((int)(r - l) / 2)));
			do
			{
				while(strcomp(x, *(a + *i)) > 0)	i++;
				while(strcomp(*(a + *j), x) > 0)	j--;
				if(i > j)	break;
				w = *i;
				*i++ = *j;
				*j-- = w;
			} while(i <= j);
			if(j - l < r - i)
			{
				if(i < r)
				{
					*(++s1) = i;
					*(++s2) = r;
				}
				r = j;
			}
			else
			{
				if(l < j)
				{
					*(++s1) = l;
					*(++s2) = j;
				}
				l = i;
			}
		} while(l < r);
	}while (s1 >= st1);
	return;
}

void idistsort(int a[], int n, int max, int min, int jun[])
{
	int m;
	int *b, *count, *p, *pp, *q;
	int *clast, *r;

	if(n <= 1 || max <= min)
	{
		fprintf(stderr, "Error : illegal data input  in idistsort()\n");
		if(n <= 1)		fprintf(stderr, "     n=%d (n > 2)\n", n);
		if(max <= min)
			fprintf(stderr, "     max=%d, min=%d (max > min)\n", max, min);
		return;
	}

	b = (int *)malloc(sizeof(int) * n);
	count = (int *)malloc(sizeof(int) * ((m = max - min) + 1));
	if(b == NULL || count == NULL)
	{
		fprintf(stderr, "Error : out of memory  in idistsort()\n");
		return;
	}

	clast = r = count + m;
	while(r >= count)	*r-- = 0;
	p = pp = b + n - 1;
	q = a + n - 1;
	while(q >= a)	(*(count + (*p-- = *q-- - min)))++;
	r = count;
	while(++r <= clast)	*r += *(r - 1);
	m = n - 1;
	while(pp >= b)	*(jun + --*(count + *pp--)) = m--;

	free((uchar *)b);
	free((uchar *)count);
}