/*	
 *	clipsort.c
 *
 *	CLiP - Common Library for P/ECE
 *	Copyright (C) 2001-2010 Naoyuki Sawa
 *
 *	* Fri Apr 13 00:10:09 JST 2007 Naoyuki Sawa
 *	- 怴婯嶌惉丅
 *	* Thu Apr 19 11:44:36 JST 2007 Naoyuki Sawa
 *	- 旕忢偵怺偄嵞婣屇傃弌偟偑敪惗偡傞応崌偑偁偭偨偺傪杊偖偨傔偺曄峏傪峴偄傑偟偨丅
 *	* Thu Apr 19 14:58:48 JST 2007 Naoyuki Sawa
 *	- 儖乕僾傪堦偐強丄while(){...}偐傜do{...}while()偵曄峏偟丄彮偟岠棪壔偟傑偟偨丅
 *	* Sun May 13 14:21:21 JST 2007 Naoyuki Sawa
 *	- 僸乕僾僜乕僩偺幚憰椺傪捛壛偟傑偟偨丅
 *	  僐儊儞僩傾僂僩偟偰偁傝傑偡偺偱丄儔僀僽儔儕僾儘僌儔儉帺懱偵偼曄壔偁傝傑偣傫丅
 *	* Mon Oct 18 21:09:33 JST 2010 Naoyuki Sawa
 *	- msort()傪捛壛偟傑偟偨丅
 */
#include "clip.h"

/*****************************************************************************
 *	僋傿僢僋僜乕僩
 *****************************************************************************/

/* * 昗弨C儔僀僽儔儕偺EPSON斉qsort()傪抲偒姺偊傑偡丅
 * - EPSON斉qsort()偵晄嬶崌偑偁傞傢偗偱偼柍偄偺偱丄偦偺傑傑偱傕惓偟偔摦嶌偟傑偡丅
 *   偟偐偟丄EPSON斉qsort()偵偼彮偟柍懯側張棟偑娷傑傟偰偄偰丄僒僀僘偲幚峴懍搙偵柍懯偑偑傝傑偡丅
 *   僋傿僢僋僜乕僩傾儖僑儕僘儉偺曌嫮傕寭偹偰丄帺暘偱CLiP斉傪幚憰偟偰傒傞偙偲偵偟傑偟偨丅
 *   傎偲傫偳EPSON斉qsort()偲摨偠偱丄堦晹偺柍懯側張棟傪嶍彍(娭悢撪偺僐儊儞僩嶲徠)偟偨偩偗偱偡丅
 * - EPSON斉仺CLiP斉傊偺抲偒姺偊偵傛傞丄僒僀僘愡栺偲崅懍壔偺岠壥偼丄埲壓偺偲偍傝偱偡丅
 *	qsort()+swap()慡懱偺儌僕儏乕儖僒僀僘
 *		EPSON斉: 196僶僀僩
 *		CLiP斉 : 128僶僀僩 (68僶僀僩愡栺)
 *	10000梫慺偺儔儞僟儉側int攝楍傪僜乕僩偡傞帪娫
 *		EPSON斉: 1852儈儕昩
 *		CLiP斉 : 1682儈儕昩 (栺10%崅懍壔)
 * * Thu Apr 19 11:44:36 JST 2007 Naoyuki Sawa
 * - 旕忢偵怺偄嵞婣屇傃弌偟偑敪惗偡傞応崌偑偁偭偨偺傪杊偖偨傔偺曄峏傪峴偭偨偙偲偵傛傝丄
 *   僒僀僘偲懍搙偺摿惈偑彮偟曄傢傝傑偟偨丅
 *	qsort()+swap()慡懱偺儌僕儏乕儖僒僀僘
 *		EPSON斉: 196僶僀僩
 *		CLiP斉 : 140僶僀僩 (56僶僀僩愡栺)
 *	10000梫慺偺儔儞僟儉側int攝楍傪僜乕僩偡傞帪娫
 *		EPSON斉: 1852儈儕昩
 *		CLiP斉 : 1645儈儕昩 (栺11%崅懍壔)
 * * Thu Apr 19 14:58:48 JST 2007 Naoyuki Sawa
 * - 儖乕僾傪堦偐強丄while(){...}偐傜do{...}while()偵曄峏偟丄彮偟岠棪壔偟傑偟偨丅
 *   偛偔傢偢偐偵懍偔側偭偨偗傟偳丄僒僀僘偼尭傝傑偣傫偱偟偨丅
 *	qsort()+swap()慡懱偺儌僕儏乕儖僒僀僘
 *		EPSON斉: 196僶僀僩
 *		CLiP斉 : 140僶僀僩 (56僶僀僩愡栺)
 *	10000梫慺偺儔儞僟儉側int攝楍傪僜乕僩偡傞帪娫
 *		EPSON斉: 1852儈儕昩
 *		CLiP斉 : 1642儈儕昩 (栺11%崅懍壔)
 */

static void
swap(unsigned char* p1, unsigned char* p2, int size) {
#if 0
//	int tmp;
//	do {
//		tmp = *p1;
//		      *p1++ = *p2;
//		              *p2++ = tmp;
//	} while(--size);
#else
	asm("
	ld.ub	%r4, [%r12]
	ld.ub	%r5, [%r13]
	ld.b	[%r13]+, %r4	; *anti-interlock*
	ld.b	[%r12]+, %r5
	sub	%r14, 1
	jrne	-5
	");
#endif
}

//-------------------------------------------------------------------------------------------------------------
//void
//qsort(void* base, size_t num, size_t width, int (*compare)(const void*, const void*))
//{
//	unsigned char* pv;	/* 僺儃僢僩傊偺億僀儞僞 */
//	unsigned char* lo;	/* 掅埵億僀儞僞 (師偵掅埵梫慺(僺儃僢僩埲壓偺梫慺)傪奿擺偡傞埵抲傊偺億僀儞僞) */
//	unsigned char* hi;	/* 崅埵億僀儞僞 (師偵崅埵梫慺(僺儃僢僩挻夁偺梫慺)傪奿擺偡傞埵抲傊偺億僀儞僞) */
//	int lo_cnt;		/* 掅埵梫慺悢 */
//	int hi_cnt;		/* 崅埵梫慺悢 */
//
//	/* 梫慺悢偑0傑偨偼1側傜偽丄壗傕偣偢偵婣傝傑偡丅
//	 * - EPSON斉偼丄2梫慺偺応崌傕摿暿埖偄偟偰丄扨弮側斾妑偲擖傟懼偊傪峴偭偰偄傑偡偑丄偦偺昁梫偼偁傝傑偣傫丅
//	 *   2梫慺偺応崌傕丄偦傟埲忋偺梫慺悢偺応崌偲摨偠丄捠忢偺張棟偱懳墳偱偒傑偡丅
//	 */
//	if(num <= 1) {
//		return;
//	}
//
//	/* 億僀儞僞偲梫慺悢傪弶婜壔偟傑偡丅
//	 * - EPSON斉偼丄攝楍偺拞墰晅嬤偲愭摢偺梫慺傪擖傟懼偊丄傕偲傕偲拞墰晅嬤偵偁偭偨抣傪僺儃僢僩偲偟偰偄傑偡丅
//	 *   尦偐傜偁傞掱搙徃弴偵暲傫偱偄傞偲壖掕偟偰丄拞墰晅嬤偵拞墰抣偑偁傞偙偲傪婜懸偟偰偄傞偺偩偲巚偄傑偡丅
//	 *   偟偐偟幚嵺偵偼偁傑傝岠壥偑柍偔丄傓偟傠梋寁側擖傟懼偊偺夞悢偑憹偊傞暘丄惈擻傪棊偲偟偰偄傞傛偆偱偡丅
//	 *   偦偙偱CLiP斉偱偼丄扨弮偵愭摢偺梫慺傪僺儃僢僩偲偟偰嵦梡偡傞偙偲偵偟傑偟偨丅
//	 */
//	pv = base;			/* 僺儃僢僩     = 愭摢 */
//	lo = pv + width;		/* 掅埵億僀儞僞 = 僺儃僢僩偺師 */
//	hi = pv + width * (num - 1);	/* 崅埵億僀儞僞 = 枛旜 */
//	lo_cnt = 0;			/* 掅埵梫慺悢   = 0 */
//	hi_cnt = 0;			/* 崅埵梫慺悢   = 0 */
//
//	/* 掅埵億僀儞僞偲崅埵億僀儞僞偑岎嵎偡傞傑偱...(懄偪丄僺儃僢僩埲奜偺慡梫慺偺掅埵or崅埵偑妋掕偡傞傑偱)
//	 * - (num-1)夞偺僇僂儞僩僟僂儞偱儖乕僾偡傞曽朄偱傕摨偠寢壥傪摼傜傟傑偡偑丄(lo<=hi)偱儖乕僾偡傞曽偑丄
//	 *   num曄悢偺惗懚婜娫傪抁偔偟丄帺摦曄悢偺儗僕僗僞妱傝摉偰嵟揔壔偑傛傝桳岠偵摥偔偙偲偑婜懸偱偒傑偡丅
//	 */
//	while(lo <= hi) { /* 拲堄!!(lo<hi)偱偼偁傝傑偣傫!! */
//		/* 掅埵億僀儞僞偺埵抲偵桳傞梫慺傪丄僺儃僢僩偲斾妑偟傑偡丅 */
//		if(compare(lo, pv) <= 0) {
//			/* 掅埵梫慺側傜偽丄掅埵億僀儞僞偺埵抲偵奿擺偟傑偡丅
//			 * 掅埵億僀儞僞偺師偺埵抲偵桳傞梫慺偑丄師夞偺斾妑懳徾偲側傝傑偡丅
//			 */
//			lo += width;
//			lo_cnt++;
//		} else {
//			/* 崅埵梫慺側傜偽丄崅埵億僀儞僞偺埵抲偵奿擺偟傑偡丅
//			 * 崅埵億僀儞僞偺埵抲偵桳偭偨梫慺偑丄師夞偺斾妑埵抲偵堏摦偟傑偡丅
//			 */
//			swap(lo, hi, width);
//			hi -= width;
//			hi_cnt++;
//		}
//	}
//
//	/* 埲忋偺張棟偑廔傢偭偨帪揰偱[僺儃僢僩,[掅埵梫慺偺暲傃],[崅埵梫慺偺暲傃]]偲側偭偰偄傑偡丅
//	 * [[掅埵梫慺偺暲傃],僺儃僢僩,[崅埵梫慺偺暲傃]]偲擖傟懼偊偰丄僺儃僢僩偺埵抲傪妋掕偟傑偡丅
//	 * - 擖傟懼偊帪偵掅埵梫慺偺暲傃弴偑曄壔偟傑偡偑丄傑偩暲傃弴偵堄枴偼側偄偺偱丄戝忎晇偱偡丅
//	 * - 傕偟掅埵梫慺偑堦偮傕柍偄応崌丄pv==hi偲側偭偰偄偰丄偙偺swap()張棟偼僟儈乕偲側傝傑偡丅
//	 */
//	swap(pv, hi, width);
//
//	/* [掅埵梫慺偺暲傃]傪僜乕僩偟傑偡丅 */
//	qsort(pv, lo_cnt, width, compare); /* 拲堄!![掅埵梫慺偺暲傃]偺愭摢傪巜偟偰偄傞偺偼丄lo偱側偔pv偱偡!! */
//
//	/* [崅埵梫慺偺暲傃]傪僜乕僩偟傑偡丅 */
//	qsort(lo, hi_cnt, width, compare); /* 拲堄!![崅埵梫慺偺暲傃]偺愭摢傪巜偟偰偄傞偺偼丄hi偱側偔lo偱偡!! */
//}
//-------------------------------------------------------------------------------------------------------------
//伀* Thu Apr 19 11:44:36 JST 2007 Naoyuki Sawa
//伀- 旕忢偵怺偄嵞婣屇傃弌偟偑敪惗偡傞応崌偑偁偭偨偺傪杊偖偨傔偺曄峏傪峴偄傑偟偨丅
//伀- 忋偺僐儊儞僩傾僂僩偟偨幚憰偼丄僋僀僢僋僜乕僩偺偄偪偽傫慺捈側幚憰偱偡丅
//伀  傾儖僑儕僘儉揑偵偼偙偺傑傑偱傕娫堘偄偱偼偁傝傑偣傫偑丄旕忢偵怺偄嵞婣屇傃弌偟偑敪惗偡傞応崌偑偁傞偲偄偆栤戣偑偁傝傑偡丅
//伀- 偳偺傛偆側働乕僗偱旕忢偵怺偄嵞婣屇傃弌偟偑敪惗偡傞偐偲偄偆偲丄偁傜偐偠傔僜乕僩偝傟偨悢楍傪僜乕僩偟傛偆偲偟偨応崌偱偡丅
//伀
//伀	<椺>	師偺傛偆側屇傃弌偟傪峴偭偨応崌傪峫偊偰傒傑偡丅
//伀
//伀			int array[10000] = { 1,2,3,...,10000 };
//伀			qsort(array, 10000, sizeof(int), compare);
//伀
//伀		嵟弶偺屇傃弌偟儗儀儖偱丄[[掅埵梫慺偺暲傃],僺儃僢僩,[崅埵梫慺偺暲傃]]偼丄埲壓偺傛偆偵側傝傑偡丅
//伀
//伀			[[(嬻)],1,[2,3,4,...,10000]]	(屇傃弌偟偺怺偝=1)
//伀
//伀		[崅埵梫慺偺暲傃]偵懳偡傞嵞婣屇傃弌偟偵拲栚偡傞偲丄師偺儗儀儖偱丄[[掅埵梫慺偺暲傃],僺儃僢僩,[崅埵梫慺偺暲傃]]偼丄埲壓偺傛偆偵側傝傑偡丅
//伀
//伀			[[(嬻)],2,[3,4,5,...,10000]]	(屇傃弌偟偺怺偝=2)
//伀
//伀		偝傜偵師偺儗儀儖偱偼丄[[掅埵梫慺偺暲傃],僺儃僢僩,[崅埵梫慺偺暲傃]]偼丄埲壓偺傛偆偵側傝傑偡丅
//伀
//伀			[[(嬻)],3,[4,5,6,...,10000]]	(屇傃弌偟偺怺偝=3)
//伀
//伀		嵟屻偵偼丄偙偆側傝傑偡丅
//伀
//伀			[[(嬻)],10000,[(嬻)]]	(屇傃弌偟偺怺偝=10000)
//伀
//伀		埲忋偺椺偺傛偆偵丄偁傜偐偠傔僜乕僩偝傟偨悢楍傪僜乕僩偟傛偆偲偡傞偲丄旕忢偵怺偄嵞婣屇傃弌偟偑敪惗偡傞応崌偑偁傝傑偡丅
//伀		悢楍偺挿偝傪N偲偡傞偲丄嵟戝N儗儀儖偺嵞婣屇傃弌偟偑敪惗偟傑偡丅(偁傜偐偠傔姰慡偵僜乕僩偝傟偰偄傞悢楍傪僜乕僩偟傛偆偲偟偨応崌)
//伀		偁傜偐偠傔姰慡偵僜乕僩偝傟偰偄傞悢楍偵尷傜偢偲傕丄偁傞掱搙僜乕僩偝傟偰偄傟偽偄傞傎偳丄嵞婣屇傃弌偟偑怺偔側傞壜擻惈偑偁傝傑偡丅
//伀
//伀		幚嵺偵偳偺偖傜偄怺偔側傞偐偼悢楍偺弶婜忬懺偵埶懚偟丄qsort()傪幚峴偟偰傒傞傑偱傢偐傜側偄偺偱丄婋尟偱偡丅
//伀		摿偵丄P/ECE偺傛偆側僗僞僢僋椞堟偺彫偝側幚峴娐嫬偱棙梡偡傞応崌偵婋尟偱偡丅
//伀
//伀- 忋弎偺栤戣傪夵慞偡傞曽朄偼丄埲壓偺偲偍傝偱偡丅
//伀	丒[掅埵梫慺偺暲傃]偲[崅埵梫慺偺暲傃]偺偆偪丄梫慺偑彮側偄曽傪嵞婣屇傃弌偟偱僜乕僩偟傑偡丅
//伀	丒梫慺偑懡偄曽偼丄尰嵼偺屇傃弌偟儗儀儖偺傑傑丄嵟弶偐傜張棟傪孞傝曉偡偙偲偱僜乕僩偟傑偡丅
//伀  偙偺傛偆偵曄峏偡傞偙偲偱丄嵞婣屇傃弌偟偺嵟戝怺偝偑丄嵟埆偱傕 log2(N) 偵梷偊傜傟傑偡丅
//伀- 偨偲偊偽丄10000梫慺偺悢楍傪僜乕僩偡傞応崌丄夵慞慜偼嵟埆10000儗儀儖偺嵞婣屇傃弌偟偑敪惗偟偰偄傑偟偨偑丄夵慞屻偼嵟埆偱傕14儗儀儖偵梷偊傜傟傑偡丅
//伀  僜乕僩懳徾偺尰幚揑側挿偝傪峫椂偡傞偲丄栺20儗儀儖埲忋偺嵞婣屇傃弌偟偑敪惗偡傞忬嫷偼傎傏桳傝摼側偄偲峫偊傜傟傞偺偱丄P/ECE偱傕廩暘偵埨慡偱偡丅
//伀- 偨偩偟丄忋弎偺夵慞偼偁偔傑偱傕儊儌儕岠棪(=嵞婣屇傃弌偟儗儀儖)偵娭偡傞傕偺偱偁傝丄帪娫岠棪偼夵慞偝傟側偄偙偲偵拲堄偟偰偔偩偝偄丅
//伀  10000梫慺偺int攝楍傪僜乕僩偡傞帪娫傪寁偭偰傒傞偲丄儔儞僟儉悢楍側傜偽栺1600儈儕昩偱偡偑丄偁傜偐偠傔僜乕僩偝傟偰偄傞偲栺15300儈儕昩偐偐傝傑偟偨丅
//伀
//伀	[嶲峫暥專丗P.J.僾儔僂僈乕挊乽昗弨俠儔僀僽儔儕 ANSI/ISO/JIS C婯奿乿乮僩僢僷儞乯弶斉 411乣412儁乕僕 杮暥]
void
qsort(void* base, size_t num, size_t width, int (*compare)(const void*, const void*))
{
	unsigned char* pv;	/* 僺儃僢僩傊偺億僀儞僞 */
	unsigned char* lo;	/* 掅埵億僀儞僞 (師偵掅埵梫慺(僺儃僢僩埲壓偺梫慺)傪奿擺偡傞埵抲傊偺億僀儞僞) */
	unsigned char* hi;	/* 崅埵億僀儞僞 (師偵崅埵梫慺(僺儃僢僩挻夁偺梫慺)傪奿擺偡傞埵抲傊偺億僀儞僞) */
	int lo_cnt;		/* 掅埵梫慺悢 */
	int hi_cnt;		/* 崅埵梫慺悢 */

	/* 梫慺悢偑0傑偨偼1側傜偽丄壗傕偣偢偵婣傝傑偡丅
	 * - EPSON斉偼丄2梫慺偺応崌傕摿暿埖偄偟偰丄扨弮側斾妑偲擖傟懼偊傪峴偭偰偄傑偡偑丄偦偺昁梫偼偁傝傑偣傫丅
	 *   2梫慺偺応崌傕丄偦傟埲忋偺梫慺悢偺応崌偲摨偠丄捠忢偺張棟偱懳墳偱偒傑偡丅
	 */
	while(num >= 2) {
		/* 億僀儞僞偲梫慺悢傪弶婜壔偟傑偡丅
		 * - EPSON斉偼丄攝楍偺拞墰晅嬤偲愭摢偺梫慺傪擖傟懼偊丄傕偲傕偲拞墰晅嬤偵偁偭偨抣傪僺儃僢僩偲偟偰偄傑偡丅
		 *   尦偐傜偁傞掱搙徃弴偵暲傫偱偄傞偲壖掕偟偰丄拞墰晅嬤偵拞墰抣偑偁傞偙偲傪婜懸偟偰偄傞偺偩偲巚偄傑偡丅
		 *   偟偐偟幚嵺偵偼偁傑傝岠壥偑柍偔丄傓偟傠梋寁側擖傟懼偊偺夞悢偑憹偊傞暘丄惈擻傪棊偲偟偰偄傞傛偆偱偡丅
		 *   偦偙偱CLiP斉偱偼丄扨弮偵愭摢偺梫慺傪僺儃僢僩偲偟偰嵦梡偡傞偙偲偵偟傑偟偨丅
		 */
		pv = base;			/* 僺儃僢僩     = 愭摢 */
		lo = pv + width;		/* 掅埵億僀儞僞 = 僺儃僢僩偺師 */
		hi = pv + width * (num - 1);	/* 崅埵億僀儞僞 = 枛旜 */
		lo_cnt = 0;			/* 掅埵梫慺悢   = 0 */
		hi_cnt = 0;			/* 崅埵梫慺悢   = 0 */

		/* 掅埵億僀儞僞偲崅埵億僀儞僞偑岎嵎偡傞傑偱...(懄偪丄僺儃僢僩埲奜偺慡梫慺偺掅埵or崅埵偑妋掕偡傞傑偱)
		 * - (num-1)夞偺僇僂儞僩僟僂儞偱儖乕僾偡傞曽朄偱傕摨偠寢壥傪摼傜傟傑偡偑丄(lo<=hi)偱儖乕僾偡傞曽偑丄
		 *   num曄悢偺惗懚婜娫傪抁偔偟丄帺摦曄悢偺儗僕僗僞妱傝摉偰嵟揔壔偑傛傝桳岠偵摥偔偙偲偑婜懸偱偒傑偡丅
		 */
		//while(lo <= hi) { /* 拲堄!!(lo<hi)偱偼偁傝傑偣傫!! */
		//伀* Thu Apr 19 14:58:48 JST 2007 Naoyuki Sawa
		//伀- (num>=2)偺忦審傛傝弶夞偼昁偢(lo<=hi)偲側傞偺偱丄while(){...}傛傝傕岠棪揑側do{...}while()偵懼偊傜傟傑偡丅
		do {
			/* 掅埵億僀儞僞偺埵抲偵桳傞梫慺傪丄僺儃僢僩偲斾妑偟傑偡丅 */
			if(compare(lo, pv) <= 0) {
				/* 掅埵梫慺側傜偽丄掅埵億僀儞僞偺埵抲偵奿擺偟傑偡丅
				 * 掅埵億僀儞僞偺師偺埵抲偵桳傞梫慺偑丄師夞偺斾妑懳徾偲側傝傑偡丅
				 */
				lo += width;
				lo_cnt++;
			} else {
				/* 崅埵梫慺側傜偽丄崅埵億僀儞僞偺埵抲偵奿擺偟傑偡丅
				 * 崅埵億僀儞僞偺埵抲偵桳偭偨梫慺偑丄師夞偺斾妑埵抲偵堏摦偟傑偡丅
				 */
				swap(lo, hi, width);
				hi -= width;
				hi_cnt++;
			}
		//}
		//伀* Thu Apr 19 14:58:48 JST 2007 Naoyuki Sawa
		//伀- (num>=2)偺忦審傛傝弶夞偼昁偢(lo<=hi)偲側傞偺偱丄while(){...}傛傝傕岠棪揑側do{...}while()偵懼偊傜傟傑偡丅
		} while(lo <= hi); /* 拲堄!!(lo<hi)偱偼偁傝傑偣傫!! */

		/* 埲忋偺張棟偑廔傢偭偨帪揰偱[僺儃僢僩,[掅埵梫慺偺暲傃],[崅埵梫慺偺暲傃]]偲側偭偰偄傑偡丅
		 * [[掅埵梫慺偺暲傃],僺儃僢僩,[崅埵梫慺偺暲傃]]偲擖傟懼偊偰丄僺儃僢僩偺埵抲傪妋掕偟傑偡丅
		 * - 擖傟懼偊帪偵掅埵梫慺偺暲傃弴偑曄壔偟傑偡偑丄傑偩暲傃弴偵堄枴偼側偄偺偱丄戝忎晇偱偡丅
		 * - 傕偟掅埵梫慺偑堦偮傕柍偄応崌丄pv==hi偲側偭偰偄偰丄偙偺swap()張棟偼僟儈乕偲側傝傑偡丅
		 */
		swap(pv, hi, width);

		/* [掅埵梫慺偺暲傃]偲[崅埵梫慺偺暲傃]偺偆偪丄梫慺偑彮側偄曽傪嵞婣屇傃弌偟偱僜乕僩偟傑偡丅
		 * 梫慺偑懡偄曽偼丄尰嵼偺屇傃弌偟儗儀儖偺傑傑丄嵟弶偐傜張棟傪孞傝曉偡偙偲偱僜乕僩偟傑偡丅
		 * - 椉曽傪嵞婣屇傃弌偟偱僜乕僩偡傞偲丄旕忢偵怺偄嵞婣偑敪惗偟偰偟傑偆応崌傪杊偖偨傔偱偡丅
		 *   嬶懱揑偵偼丄偙偺娭悢偺忋偵彂偄偨僐儊儞僩傪嶲徠偟偰偔偩偝偄丅
		 */
		if(lo_cnt <= hi_cnt) {
			/* [掅埵梫慺偺暲傃]傪僜乕僩偟傑偡丅 */
			qsort(pv, lo_cnt, width, compare); /* 拲堄!![掅埵梫慺偺暲傃]偺愭摢傪巜偟偰偄傞偺偼丄lo偱側偔pv偱偡!! */
			/* [崅埵梫慺偺暲傃]傪僜乕僩偟傑偡丅 */
			base = lo, num = hi_cnt;           /* 拲堄!![崅埵梫慺偺暲傃]偺愭摢傪巜偟偰偄傞偺偼丄hi偱側偔lo偱偡!! */
		} else {
			/* [崅埵梫慺偺暲傃]傪僜乕僩偟傑偡丅 */
			qsort(lo, hi_cnt, width, compare); /* 拲堄!![崅埵梫慺偺暲傃]偺愭摢傪巜偟偰偄傞偺偼丄hi偱側偔lo偱偡!! */
			/* [掅埵梫慺偺暲傃]傪僜乕僩偟傑偡丅 */
			base = pv, num = lo_cnt;           /* 拲堄!![掅埵梫慺偺暲傃]偺愭摢傪巜偟偰偄傞偺偼丄lo偱側偔pv偱偡!! */
		}
	}
}

/*****************************************************************************
 *	僸乕僾僜乕僩
 *****************************************************************************/

#if 0	/*{{僸乕僾僜乕僩偺幚憰椺*/

* Sun May 13 14:21:21 JST 2007 Naoyuki Sawa
- 乽僸乕僾僜乕僩 - Wikipedia乿偺媅帡僐乕僪傪嶲峫偵丄嵟揔壔偟偰嶌惉偟傑偟偨丅
  (URL: http://ja.wikipedia.org/w/index.php?title=%E3%83%92%E3%83%BC%E3%83%97%E3%82%BD%E3%83%BC%E3%83%88&oldid=12248591)
  嵟揔壔偟偨庡側揰偼丄恊傗巕偺梫慺傪巜偟帵偡偨傔偺僀儞僨僋僗傪巊傢偢偵丄偡傋偰億僀儞僞偱張棟偟偰崅懍壔傪恾偭偨偙偲偱偡丅
- 僸乕僾僜乕僩偑僋傿僢僋僜乕僩傛傝傕桪傟偰偄傞揰偼丄僨乕僞偺偐偨傛傝偑懍搙偵偁傑傝塭嬁偟側偄偙偲偱偡丅
  僋傿僢僋僜乕僩偼丄堦條偵儔儞僟儉側悢楍偺僜乕僩偑偄偪偽傫憗偔丄尦乆弴楍偺僜乕僩偼抶偔丄媡弴偺僜乕僩偑傕偭偲傕抶偄偱偡丅
  僸乕僾僜乕僩偼丄偳偺働乕僗偵懳偟偰傕偍偍傛偦摨偠偖傜偄偺懍搙偱姰椆偟傑偡丅
- 偟偐偟幚嵺偵偼丄僋傿僢僋僜乕僩傛傝傕僸乕僾僜乕僩傪慖戰偡傞応柺偼柍偄偲巚偄傑偡丅
  僋傿僢僋僜乕僩偵晄棙側媡弴偺僜乕僩偱偁偭偰傕丄僋傿僢僋僜乕僩偺曽偑僸乕僾僜乕僩傛傝傕擇攞偖傜偄憗偔姰椆偱偒傞傛偆偱偡丅
  堦條偵儔儞僟儉側悢楍偺僜乕僩偺応崌偼丄50攞埲忋偺懍搙嵎偑晅偄偰偟傑偄傑偡丅
  (Windows偱幚尡偟偨応崌偼偙偙傑偱偺懍搙嵎偼晅偐側偐偭偨偺偱偡偑丄P/ECE偱偼側偤偐忋弎偺傛偆側戝嵎偵側偭偰偟傑偄傑偟偨丅)
- 埲壓偺僐乕僪偼丄惓偟偔摦偔偙偲傪妋擣嵪傒偱偡偑丄幚嵺偵巊偆偙偲偼柍偄偲巚偄傑偡丅
  儕儞僋僒僀僘偑憹偊側偄傛偆偵僐儊儞僩傾僂僩偟偰偁傝傑偡偺偱丄傕偟巊偆応崌偼傾僾儕働乕僔儑儞偵僐僺乕偟偰巊偭偰偔偩偝偄丅

static void
make_heap(unsigned char* base, unsigned char* last, size_t width, int (*compare)(const void*, const void*), unsigned char* parent)
{
	unsigned char* child1;
	unsigned char* child2;

	/* 嵍偺巕偑桳傟偽... */
	child1 = (base + (parent - base) * 2) + width;
	if(child1 <= last) {
		/* 嵍偺巕偺僣儕乕傪僜乕僩偟傑偡丅 */
		make_heap(base, last, width, compare, child1);
		/* 塃偺巕偑桳傟偽... */
		child2 = child1 + width;
		if(child2 <= last) {
			/* 塃偺巕偺僣儕乕傪僜乕僩偟傑偡丅 */
			make_heap(base, last, width, compare, child2);
			/* child1偑戝偒偄曽偺巕傪巜偡傛偆偵偟傑偡丅 */
			if(compare(child1, child2) < 0) {
				child1 = child2;
			}
		}
		/* 戝偒偄曽偺巕偑恊傛傝傕戝偒偗傟偽... */
		if(compare(parent, child1) < 0) {
			/* 戝偒偄曽偺巕偲恊傪擖傟懼偊傑偡丅 */
			swap(parent, child1, width);
			//make_heap(base, last, width, compare, child1);
			//仺巕偺僣儕乕偺僜乕僩偼師夞偵峴偆偺偱晄梫偱偡丅
		}
	}
}

void
hsort(void* _base, size_t num, size_t width, int (*compare)(const void*, const void*))
{
	unsigned char* base = _base;
	unsigned char* last = base + (width * (num - 1));

	while(base < last) {
		/* 僣儕乕慡懱傪崀弴偵僜乕僩偟傑偡丅 */
		make_heap(base, last, width, compare, base);
		/* 嵟戝梫慺傪僣儕乕偺枛旜偵愗傝棧偟傑偡丅 */
		swap(base, last, width);
		last -= width;
	}
}

#endif	/*}}僸乕僾僜乕僩偺幚憰椺*/

/*****************************************************************************
 *	儅乕僕僜乕僩
 *****************************************************************************/

/* * Mon Oct 18 15:12:52 JST 2010 Naoyuki Sawa
 * - msort()娭悢傪幚憰偡傞嵺偵嶲峫偵偟偨Web僒僀僩傪丄僥僉僗僩壔偟偰婰榐偟偰偍偔偙偲偵偟傑偡丅
 *   亀乮俵俙倃忋偵偍偗傞乯傾儖僑儕僘儉揑栤戣偵偍偗傞儐乕僓乕僀儞僞乕僼僃乕僗偺夵椙亁偺拞偺丄
 *   丂(http://www.th.cs.meiji.ac.jp/researches/2005/omoto/index.html)
 *   乽8. 儅乕僕僜乕僩乿偺儁乕僕偐傜丄堷梡偝偣偰偄偨偩偒傑偟偨丅
 *   丂(http://www.th.cs.meiji.ac.jp/researches/2005/omoto/mergesort.html)
 * - 堦斒揑偵儅乕僕僜乕僩偼丄嵞婣傪梡偄偰幚憰偡傞偺偱偡偗傟偳丄忋婰僒僀僩偺僒儞僾儖僜乕僗偼丄嵞婣傪梡偄側偄偱幚憰偟偰偄傑偡丅
 *   傑偨丄儊儌儕妋曐偺巇慻傒傕敾傝傗偡偔丄儕僜乕僗偺尷傜傟偨儅僀僐儞岦偒偺幚憰偩偲巚偄傑偡丅
 * 
 * 	劕劒劒劒劒劒劒劒劒劒劒劒劒劒劒劒劒劒劒劒劒劒劒劒劒劒劒劒劒劒劒劒劒劒劒劒劒劒劒劒劒劒劒劒劒劒劒劒劒劒劒劒劒劒劒劒劒劒劒劒劖
 * 	劔儅乕僕僜乕僩														劔
 * 	劘劒劒劒劒劒劒劒劒劒劒劒劒劒劒劒劒劒劒劒劒劒劒劒劒劒劒劒劒劒劒劒劒劒劒劒劒劒劒劒劒劒劒劒劒劒劒劒劒劒劒劒劒劒劒劒劒劒劒劒劗
 * 
 * 	劇劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劉
 * 	劆儅乕僕僜乕僩偲偼丠													劆
 * 	劋劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劊
 * 
 * 	儅乕僕僜乕僩偼丄僨乕僞楍傪擇偮偵暘妱偟丄偦傟傜傪嵞傃儅乕僕偡傞乮暪崌偡傞乯帪偵戝偒偝偺弴偵僨乕僞傪庢傝弌偟偰暲傋傞丅
 * 	暘妱偝傟偨偦傟偧傟偑戝偒偝偺弴偵暲傫偱偄傟偽儅乕僕偟偨傕偺傕戝偒偝偺弴偵暲傇偺偱丄暘妱偝傟偨傕偺偵懳偟偰傕
 * 	儅乕僕僜乕僩乮傗丄偦偺懠偺僜乕僩乧椺偊偽暘妱屻偺僨乕僞悢偑俀屄偲偐俁屄偺応崌偼扨弮側斾妑偱嵪傓乯傪嵞婣揑偵揔梡偡傟偽椙偄丅
 * 	僜乕僩偑斾妑揑崅懍偱丄摨埵偺傕偺偺弴彉偑曐懚偝傟傞偲偄偆惈幙偑偁傞丅
 * 
 * 	劇劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劉
 * 	劆峫偊曽														劆
 * 	劋劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劊
 * 
 * 	姶妎偲偟偰偼丄乽俀杮偺攝楍傪梡堄偟丄暘妱偝傟偨僲乕僪偢偮僜乕僩傪峴偆乿偲偄偭偨姶偠偱偁傞丅
 * 
 * 	崱丄師偺傛偆側攝楍偑懚嵼偡傞偲偡傞丅
 * 
 * 		劇劅劍劅劍劅劍劅劍劅劍劅劍劅劍劅劉
 * 		劆係劆侾劆俀劆俇劆俋劆俈劆俁劆俉劆
 * 		劋劅劏劅劏劅劏劅劏劅劏劅劏劅劏劅劊
 * 		劇劅劍劅劍劅劍劅劍劅劍劅劍劅劍劅劉
 * 		劆丂劆丂劆丂劆丂劆丂劆丂劆丂劆丂劆
 * 		劋劅劏劅劏劅劏劅劏劅劏劅劏劅劏劅劊
 * 
 * 	偙傟傪嵶偐偔暘妱偟偰偄偔偺偩偑丄傑偢丄俀偱暘妱偡傞丅
 * 
 * 		劕劒劧劒劚劒劧劒劚劒劧劒劚劒劧劒劖
 * 		劔係劆侾劔俀劆俇劔俋劆俈劔俁劆俉劔
 * 		劘劒劯劒劤劒劯劒劤劒劯劒劤劒劯劒劗
 * 		劇劅劍劅劍劅劍劅劍劅劍劅劍劅劍劅劉
 * 		劆丂劆丂劆丂劆丂劆丂劆丂劆丂劆丂劆
 * 		劋劅劏劅劏劅劏劅劏劅劏劅劏劅劏劅劊
 * 
 * 	暘妱偝傟偨斖埻撪偱丄傕偆侾偮梡堄偝傟偨攝楍偵僜乕僩偟偨抣傪擖傟偰偄偔丅
 * 
 * 		劕劒劧劒劚劒劧劒劚劒劧劒劚劒劧劒劖
 * 		劔係劆侾劔俀劆俇劔俋劆俈劔俁劆俉劔
 * 		劘劒劯劒劤劒劯劒劤劒劯劒劤劒劯劒劗
 * 		伀丂丂丂伀丂丂丂伀丂丂丂伀丂丂丂伀
 * 		劇劅劍劅劍劅劍劅劍劅劍劅劍劅劍劅劉
 * 		劆侾劆係劆俀劆俇劆俈劆俋劆俁劆俉劆
 * 		劋劅劏劅劏劅劏劅劏劅劏劅劏劅劏劅劊
 * 
 * 	師偵怴偟偔抣傪曐帩偟偨攝楍傪暘妱偡傞偺偩偑丄俀亊俀亖係偱暘妱偡傞丅
 * 
 * 		劇劅劍劅劍劅劍劅劍劅劍劅劍劅劍劅劉
 * 		劆係劆侾劆俀劆俇劆俋劆俈劆俁劆俉劆
 * 		劋劅劏劅劏劅劏劅劏劅劏劅劏劅劏劅劊
 * 		劕劒劧劒劧劒劧劒劚劒劧劒劧劒劧劒劖
 * 		劔侾劆係劆俀劆俇劔俈劆俋劆俁劆俉劔
 * 		劘劒劯劒劯劒劯劒劤劒劯劒劯劒劯劒劗
 * 
 * 	暘妱偝傟偨斖埻撪偱丄尦偺攝楍偵僜乕僩偟偨抣傪擖傟偰偄偔丅
 * 
 * 		劇劅劍劅劍劅劍劅劍劅劍劅劍劅劍劅劉
 * 		劆侾劆俀劆係劆俇劆俁劆俈劆俉劆俋劆
 * 		劋劅劏劅劏劅劏劅劏劅劏劅劏劅劏劅劊
 * 		仾丂丂丂丂丂丂丂仾丂丂丂丂丂丂丂仾
 * 		劕劒劧劒劧劒劧劒劚劒劧劒劧劒劧劒劖
 * 		劔侾劆係劆俀劆俇劔俈劆俋劆俁劆俉劔
 * 		劘劒劯劒劯劒劯劒劤劒劯劒劯劒劯劒劗
 * 
 * 	師偵怴偟偔抣傪曐帩偟偨尦偺攝楍傪暘妱偡傞丅係亊俀亖俉偱暘妱偡傞丅
 * 
 * 		劕劒劧劒劧劒劧劒劧劒劧劒劧劒劧劒劖
 * 		劔侾劆俀劆係劆俇劆俁劆俈劆俉劆俋劔
 * 		劘劒劯劒劯劒劯劒劯劒劯劒劯劒劯劒劗
 * 		劇劅劍劅劍劅劍劅劍劅劍劅劍劅劍劅劉
 * 		劆侾劆係劆俀劆俇劆俈劆俋劆俁劆俉劆
 * 		劋劅劏劅劏劅劏劅劏劅劏劅劏劅劏劅劊
 * 
 * 	暘妱偝傟偨斖埻撪偱丄傕偆侾偮梡堄偝傟偨攝楍偵僜乕僩偟偨抣傪擖傟偰偄偔丅
 * 
 * 		劕劒劧劒劧劒劧劒劧劒劧劒劧劒劧劒劖
 * 		劔侾劆俀劆係劆俇劆俁劆俈劆俉劆俋劔
 * 		劘劒劯劒劯劒劯劒劯劒劯劒劯劒劯劒劗
 * 		伀丂丂丂丂丂丂丂丂丂丂丂丂丂丂丂伀
 * 		劇劅劍劅劍劅劍劅劍劅劍劅劍劅劍劅劉
 * 		劆侾劆俀劆俁劆係劆俇劆俈劆俉劆俋劆
 * 		劋劅劏劅劏劅劏劅劏劅劏劅劏劅劏劅劊
 * 
 * 	師偵怴偟偔抣傪曐帩偟偨攝楍傪暘妱偡傞偺偩偑丄梫慺悢偑俉偱偁傞偺偱俉偱暘妱偡傞丅
 * 
 * 		劇劅劍劅劍劅劍劅劍劅劍劅劍劅劍劅劉
 * 		劆侾劆俀劆係劆俇劆俁劆俈劆俉劆俋劆
 * 		劋劅劏劅劏劅劏劅劏劅劏劅劏劅劏劅劊
 * 		劕劒劧劒劧劒劧劒劧劒劧劒劧劒劧劒劖
 * 		劔侾劆俀劆俁劆係劆俇劆俈劆俉劆俋劔
 * 		劘劒劯劒劯劒劯劒劯劒劯劒劯劒劯劒劗
 * 
 * 	暘妱偝傟偨斖埻撪偱丄尦偺攝楍偵僜乕僩偟偨抣傪擖傟偰偄偔丅
 * 
 * 		劇劅劍劅劍劅劍劅劍劅劍劅劍劅劍劅劉
 * 		劆侾劆俀劆俁劆係劆俇劆俈劆俉劆俋劆
 * 		劋劅劏劅劏劅劏劅劏劅劏劅劏劅劏劅劊
 * 		仾丂丂丂丂丂丂丂丂丂丂丂丂丂丂丂仾
 * 		劕劒劧劒劧劒劧劒劧劒劧劒劧劒劧劒劖
 * 		劔侾劆俀劆俁劆係劆俇劆俈劆俉劆俋劔
 * 		劘劒劯劒劯劒劯劒劯劒劯劒劯劒劯劒劗
 * 
 * 	尦偺攝楍傪暘妱偡傞嵺偵丄暘妱偺斖埻偑梫慺悢傪挻偊偰偄傞応崌丄僜乕僩廔椆偲側傞丅
 * 
 * 	埲忋偑儅乕僕僜乕僩偺棳傟偱偁傞丅
 * 
 * 	儅乕僕僜乕僩偺傾儖僑儕僘儉偼埲壓偺傛偆偵婰弎偱偒傞丅
 * 
 * 		void sort() {							// 儅乕僕僜乕僩(徃弴)
 * 			int seqsize = 1;					// 戝偒偝偺弶婜抣傪1偲偡傞
 * 			while (seqsize < length) {				// 僜乕僩偡傞戝偒偝偑僨乕僞傛傝傕彫偝偗傟偽丆
 * 				mergeseqs(seqsize, a, b);			// 巜掕偝傟偨戝偒偝偱攝楍a偐傜攝楍b傊儅乕僕
 * 				mergeseqs(2 * seqsize, b, a);			// 巜掕偝傟偨2攞偺戝偒偝偱攝楍b偐傜攝楍a傊儅乕僕
 * 				seqsize = 4 * seqsize;				// 戝偒偝傪4攞偵偡傞丏
 * 			}
 * 		}
 * 
 * 		void mergeseqs(int size, int from [], int to []) {		// from攝楍偐傜儅乕僕偱to攝楍傪嶌傞
 * 			int i, j, k, iend, jend;
 * 			int start = 0;
 * 			while (start < length) {
 * 				i = start;					// i: 儅乕僕偝傟傞楍偺巒傑傝
 * 				j = start + size;				// j: 儅乕僕偝傟傞傕偆堦偮偺楍偺巒傑傝
 * 				k = start;					// k: 儅乕僕偟偨寢壥偺楍偺巒傑傝
 * 				iend = Math.min(start + size, length);		// 懳徾偲偡傞攝楍梫慺偺嵟屻傪寁嶼
 * 				jend = Math.min(start + 2 * size, length);	// 懳徾偲偡傞攝楍梫慺偺嵟屻傪寁嶼
 * 				while (i < iend && j < jend) {			// 儅乕僕偡傞楍偑2偮偁傞応崌
 * 					if (from[i] <= from[j]) {
 * 						to[k] = from[i];		// 彫偝偄抣偺曽傪僐僺乕
 * 						i++;
 * 						k++;
 * 					} else {
 * 						to[k] = from[j];		// 彫偝偄抣偺曽傪僐僺乕
 * 						j++;
 * 						k++;
 * 					}
 * 				}
 * 				while (i < iend) {				// 儅乕僕偡傞楍偑1偮偩偗偺応崌
 * 					to[k] = from[i];			// 抣偺僐僺乕
 * 					i++;
 * 					k++;
 * 				}
 * 				while (j < jend) {				// 儅乕僕偡傞楍偑1偮偩偗偺応崌
 * 					to[k] = from[j];			// 抣偺僐僺乕
 * 					j++;
 * 					k++;
 * 				}
 * 				start = start + 2 * size;			// 怴偨側奐巒揰傪愝掕
 * 			}
 * 		}
 * 
 * 	仸僾儘僌儔儉堷梡
 * 	Lecture of Computer Programming I by Hiroshi Ichiji 
 * 	(http://lecture.ecc.u-tokyo.ac.jp/~cichiji/cp-01/cp-01.html)
 */

static void
mergeseqs(size_t size, const unsigned char* from, unsigned char* to, size_t length, size_t width, int (*compare)(const void*, const void*))
{
	size_t i;
	size_t j;
	size_t k;
	size_t iend;
	size_t jend;

	for(jend = 0; jend < length; /** no job **/) {
		i    = k = jend;
		iend = j = i + size;
		jend     = j + size;
		if(iend > length) {
			iend = length;
		}
		if(jend > length) {
			jend = length;
		}
		while((i < iend) && (j < jend)) {
			if(compare(&from[i * width], &from[j * width]) <= 0) {
				memcpy(&to[k++ * width], &from[i++ * width], width);
			} else {
				memcpy(&to[k++ * width], &from[j++ * width], width);
			}
		}
		if(i < iend) {
			memcpy(&to[k * width], &from[i * width], (iend - i) * width);
		}
		if(j < jend) {
			memcpy(&to[k * width], &from[j * width], (jend - j) * width);
		}
	}
}

void
msort(void* a, size_t length, size_t width, int (*compare)(const void*, const void*))
{
	void* b;
	size_t seqsize;

	b = malloc(length * width);
	if(!b) {
		DIE();
	}
	for(seqsize = 1; seqsize < length; /** no job **/) {
		mergeseqs(seqsize, a, b, length, width, compare);
		seqsize *= 2;
		mergeseqs(seqsize, b, a, length, width, compare);
		seqsize *= 2;
	}
	free(b);
}

