/*	
 *	clipsort.c
 *
 *	CLiP - Common Library for P/ECE
 *	Copyright (C) 2001-2016 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()傪捛壛偟傑偟偨丅
 *	* Wed Nov 19 20:53:11 JST 2014 Naoyuki Sawa
 *	- qsort_r()傪捛壛偟丄qsort()偼qsort_r()傊偺屇傃弌偟偵曄峏偟傑偟偨丅
 *	  qsort_r()偺愰尵偼丄include/stdlib.h偵桳傝傑偡丅
 *	- qsort_r()偼丄glibc僶乕僕儑儞2.8偱捛壛偝傟偨娭悢偱偡丅
 *	  徻嵶偼丄乽Section: Linux Programmer's Manual (3) - QSORT乿(http://linuxjm.sourceforge.jp/html/LDP_man-pages/man3/qsort.3.html)傪嶲徠偟偰偔偩偝偄丅
 *	* Thu Jan 08 21:00:51 JST 2015 Naoyuki Sawa
 *	- qsort()偲qsort_r()傪傾僙儞僽儔壔偟傑偟偨丅僐乕僪僒僀僘偑24僶僀僩彫偝偔側傝丄張棟懍搙偑栺4.5%憗偔側傝傑偟偨丅
 *	- Visual C++ 6.0偱價儖僪偡傞帪偺偨傔偵丄qsort_r()偺愰尵傪捛壛偟傑偟偨丅
 *	  P/ECE偱價儖僪偡傞帪偼丄include/stdlib.h偱qsort_r()偑愰尵偝傟偰偄傞偺偱栤戣桳傝傑偣傫偑丄
 *	  Visual C++ 6.0偱價儖僪偡傞帪偼丄Visual C++ 6.0偺stdlib.h偵偼qsort_r()偑娷傑傟偰偄側偄偺偱丄qsort()偐傜qsort_r()傊偺慜曽嶲徠偑寈崘偵側傞偨傔偱偡丅
 *	  偙偙偱qsort_r()傪愰尵偡傞偙偲偵傛傝丄Visual C++ 6.0偱價儖僪偡傞帪傕寈崘偑弌側偔側傝傑偟偨丅
 *	  彯丄P/ECE偱價儖僪偡傞帪傕偙偙偱愰尵偝傟偰偄偰傕奞偼柍偄偺偱偡偑丄嵟彫尷偲偡傞偨傔偵丄P/ECE偱價儖僪偡傞帪偼偙偙偱偼愰尵偟側偄偙偲偵偟傑偟偨丅
 *	* Fri Jan 09 00:00:00 JST 2015 Naoyuki Sawa
 *	- Asm斉qsort()傪嵟揔壔偟傑偟偨丅僐乕僪僒僀僘偑偝傜偵8僶僀僩彫偝偔側傝傑偟偨丅
 *	* Fri Jun 10 21:42:30 JST 2016 Naoyuki Sawa
 *	- 婛懚偺hsort()偲msort()傪丄heapsort()偲mergesort()偵柤慜曄峏偟丄/clip/include/stdlib.h偱愰尵偡傞傛偆偵偟傑偟偨丅
 *	  徻嵶偼丄clipsort.c偺乽僸乕僾僜乕僩偲儅乕僕僜乕僩偵偮偄偰(2016/06/10)乿傪嶲徠偟偰壓偝偄丅
 *	- clipsort.c偺堦斣壓偵丄乽僥僗僩僗僀乕僩乿傪捛婰偟傑偟偨丅
 *	* Sat Jun 11 20:47:59 JST 2016 Naoyuki Sawa
 *	- clipsort.c偺堦斣壓偵丄乽懍搙寁應寢壥(2016/06/11)乿傪捛婰偟傑偟偨丅
 *	  Win10(x64)偲P/ECE偱丄奺娭悢偺懍搙傪寁應偟偨寢壥偲丄峫嶡偱偡丅
 */
#include "clip.h"

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

//{{2016/06/10嶍彍:clipstdw.h偱愰尵偟偨偺偱丄偙偙偱偺愰尵偼晄梫偵側偭偰偄傑偟偨丅
//#ifdef  _MSC_VER
//// * Thu Jan 08 21:00:51 JST 2015 Naoyuki Sawa
//// - Visual C++ 6.0偱價儖僪偡傞帪偺偨傔偵丄qsort_r()偺愰尵傪捛壛偟傑偟偨丅
////   P/ECE偱價儖僪偡傞帪偼丄include/stdlib.h偱qsort_r()偑愰尵偝傟偰偄傞偺偱栤戣桳傝傑偣傫偑丄
////   Visual C++ 6.0偱價儖僪偡傞帪偼丄Visual C++ 6.0偺stdlib.h偵偼qsort_r()偑娷傑傟偰偄側偄偺偱丄qsort()偐傜qsort_r()傊偺慜曽嶲徠偑寈崘偵側傞偨傔偱偡丅
////   偙偙偱qsort_r()傪愰尵偡傞偙偲偵傛傝丄Visual C++ 6.0偱價儖僪偡傞帪傕寈崘偑弌側偔側傝傑偟偨丅
////   彯丄P/ECE偱價儖僪偡傞帪傕偙偙偱愰尵偝傟偰偄偰傕奞偼柍偄偺偱偡偑丄嵟彫尷偲偡傞偨傔偵丄P/ECE偱價儖僪偡傞帪偼偙偙偱偼愰尵偟側偄偙偲偵偟傑偟偨丅
//void qsort_r(void* base, size_t num, size_t width, int (*compare)(const void*, const void*, void*), void* arg);
//#endif//_MSC_VER
//}}2016/06/10嶍彍:clipstdw.h偱愰尵偟偨偺偱丄偙偙偱偺愰尵偼晄梫偵側偭偰偄傑偟偨丅

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

#ifndef PIECE
static void xchg(unsigned char* p1, unsigned char* p2, int size) {
	int tmp;
	do {
		tmp = *p1;
		      *p1++ = *p2;
		              *p2++ = tmp;
	} while(--size);
}
#else /*PIECE*/
/*static*/ void xchg(unsigned char* p1, unsigned char* p2, int size);
asm("
		.code
		.align		1
xchg:
		sub		%r14, 1			;//%psr(Z) := size--	劅劉
		 ld.b		%r10, [%r12]		;//			丂劆
		 ld.b		%r11, [%r13]		;//			丂劆
		 ld.b		[%r13]+, %r10		;//			丂劆	*anti-interlock*
		 ld.b		[%r12]+, %r11		;//			丂劆
		jrne.d		-4			;//			仼劎
		sub		%r14, 1			;//%psr(Z) := size--	劅劊	*delay
		ret
");
#endif /*PIECE*/

//-------------------------------------------------------------------------------------------------------------
#ifndef PIECE
//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 {
//			/* 崅埵梫慺側傜偽丄崅埵億僀儞僞偺埵抲偵奿擺偟傑偡丅
//			 * 崅埵億僀儞僞偺埵抲偵桳偭偨梫慺偑丄師夞偺斾妑埵抲偵堏摦偟傑偡丅
//			 */
//			xchg(lo, hi, width);
//			hi -= width;
//			hi_cnt++;
//		}
//	}
//
//	/* 埲忋偺張棟偑廔傢偭偨帪揰偱[僺儃僢僩,[掅埵梫慺偺暲傃],[崅埵梫慺偺暲傃]]偲側偭偰偄傑偡丅
//	 * [[掅埵梫慺偺暲傃],僺儃僢僩,[崅埵梫慺偺暲傃]]偲擖傟懼偊偰丄僺儃僢僩偺埵抲傪妋掕偟傑偡丅
//	 * - 擖傟懼偊帪偵掅埵梫慺偺暲傃弴偑曄壔偟傑偡偑丄傑偩暲傃弴偵堄枴偼側偄偺偱丄戝忎晇偱偡丅
//	 * - 傕偟掅埵梫慺偑堦偮傕柍偄応崌丄pv==hi偲側偭偰偄偰丄偙偺xchg()張棟偼僟儈乕偲側傝傑偡丅
//	 */
//	xchg(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*)) {
//{{2014/11/19捛壛:qsort_r()傪捛壛偟丄qsort()偼qsort_r()傊偺屇傃弌偟偵曄峏偟傑偟偨丅qsort_r()偺愰尵偼丄include/stdlib.h偵桳傝傑偡丅
	qsort_r(base, num, width, (int (*)(const void*, const void*, void*))compare, NULL);	//qsort()偲qsort_r()偼丄compare娭悢偺宍幃偑堎側傝傑偡偑丄'cdecl屇弌婯栺'側傜偽丄qsort()宍幃偺compare娭悢偵偍偄偰丄梋暘側堷悢偑柍帇偝傟傞偺偱栤戣偁傝傑偣傫丅
}
void qsort_r(void* base, size_t num, size_t width, int (*compare)(const void*, const void*, void*), void* arg) {
//}}2014/11/19捛壛:qsort_r()傪捛壛偟丄qsort()偼qsort_r()傊偺屇傃弌偟偵曄峏偟傑偟偨丅qsort_r()偺愰尵偼丄include/stdlib.h偵桳傝傑偡丅
	unsigned char* pv;	/* 僺儃僢僩傊偺億僀儞僞 */
	unsigned char* lo;	/* 掅埵億僀儞僞 (師偵掅埵梫慺(僺儃僢僩埲壓偺梫慺)傪奿擺偡傞埵抲傊偺億僀儞僞) */
	unsigned char* hi;	/* 崅埵億僀儞僞 (師偵崅埵梫慺(僺儃僢僩挻夁偺梫慺)傪奿擺偡傞埵抲傊偺億僀儞僞) */
	unsigned lo_cnt;	/* 掅埵梫慺悢 */
	unsigned 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 {
			/* 掅埵億僀儞僞偺埵抲偵桳傞梫慺傪丄僺儃僢僩偲斾妑偟傑偡丅 */
//{{2014/11/19曄峏:qsort_r()傪捛壛偟丄qsort()偼qsort_r()傊偺屇傃弌偟偵曄峏偟傑偟偨丅qsort_r()偺愰尵偼丄include/stdlib.h偵桳傝傑偡丅
//			if((*compare)(lo, pv) <= 0) {
//伀2014/11/19曄峏:qsort_r()傪捛壛偟丄qsort()偼qsort_r()傊偺屇傃弌偟偵曄峏偟傑偟偨丅qsort_r()偺愰尵偼丄include/stdlib.h偵桳傝傑偡丅
			if((*compare)(lo, pv, arg) <= 0) {
//}}2014/11/19曄峏:qsort_r()傪捛壛偟丄qsort()偼qsort_r()傊偺屇傃弌偟偵曄峏偟傑偟偨丅qsort_r()偺愰尵偼丄include/stdlib.h偵桳傝傑偡丅
				/* 掅埵梫慺側傜偽丄掅埵億僀儞僞偺埵抲偵奿擺偟傑偡丅
				 * 掅埵億僀儞僞偺師偺埵抲偵桳傞梫慺偑丄師夞偺斾妑懳徾偲側傝傑偡丅
				 */
				lo += width;
				lo_cnt++;
			} else {
				/* 崅埵梫慺側傜偽丄崅埵億僀儞僞偺埵抲偵奿擺偟傑偡丅
				 * 崅埵億僀儞僞偺埵抲偵桳偭偨梫慺偑丄師夞偺斾妑埵抲偵堏摦偟傑偡丅
				 */
				xchg(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偲側偭偰偄偰丄偙偺xchg()張棟偼僟儈乕偲側傝傑偡丅
		 */
		xchg(pv, hi, width);

		/* [掅埵梫慺偺暲傃]偲[崅埵梫慺偺暲傃]偺偆偪丄梫慺偑彮側偄曽傪嵞婣屇傃弌偟偱僜乕僩偟傑偡丅
		 * 梫慺偑懡偄曽偼丄尰嵼偺屇傃弌偟儗儀儖偺傑傑丄嵟弶偐傜張棟傪孞傝曉偡偙偲偱僜乕僩偟傑偡丅
		 * - 椉曽傪嵞婣屇傃弌偟偱僜乕僩偡傞偲丄旕忢偵怺偄嵞婣偑敪惗偟偰偟傑偆応崌傪杊偖偨傔偱偡丅
		 *   嬶懱揑偵偼丄偙偺娭悢偺忋偵彂偄偨僐儊儞僩傪嶲徠偟偰偔偩偝偄丅
		 */
		if(lo_cnt <= hi_cnt) {
			/* [掅埵梫慺偺暲傃]傪僜乕僩偟傑偡丅 */
//{{2014/11/19曄峏:qsort_r()傪捛壛偟丄qsort()偼qsort_r()傊偺屇傃弌偟偵曄峏偟傑偟偨丅qsort_r()偺愰尵偼丄include/stdlib.h偵桳傝傑偡丅
//			qsort(pv, lo_cnt, width, compare); /* 拲堄!![掅埵梫慺偺暲傃]偺愭摢傪巜偟偰偄傞偺偼丄lo偱側偔pv偱偡!! */
//伀2014/11/19曄峏:qsort_r()傪捛壛偟丄qsort()偼qsort_r()傊偺屇傃弌偟偵曄峏偟傑偟偨丅qsort_r()偺愰尵偼丄include/stdlib.h偵桳傝傑偡丅
			qsort_r(pv, lo_cnt, width, compare, arg); /* 拲堄!![掅埵梫慺偺暲傃]偺愭摢傪巜偟偰偄傞偺偼丄lo偱側偔pv偱偡!! */
//}}2014/11/19曄峏:qsort_r()傪捛壛偟丄qsort()偼qsort_r()傊偺屇傃弌偟偵曄峏偟傑偟偨丅qsort_r()偺愰尵偼丄include/stdlib.h偵桳傝傑偡丅
			/* [崅埵梫慺偺暲傃]傪僜乕僩偟傑偡丅 */
			base = lo, num = hi_cnt;           /* 拲堄!![崅埵梫慺偺暲傃]偺愭摢傪巜偟偰偄傞偺偼丄hi偱側偔lo偱偡!! */
		} else {
			/* [崅埵梫慺偺暲傃]傪僜乕僩偟傑偡丅 */
//{{2014/11/19曄峏:qsort_r()傪捛壛偟丄qsort()偼qsort_r()傊偺屇傃弌偟偵曄峏偟傑偟偨丅qsort_r()偺愰尵偼丄include/stdlib.h偵桳傝傑偡丅
//			qsort(lo, hi_cnt, width, compare); /* 拲堄!![崅埵梫慺偺暲傃]偺愭摢傪巜偟偰偄傞偺偼丄hi偱側偔lo偱偡!! */
//伀2014/11/19曄峏:qsort_r()傪捛壛偟丄qsort()偼qsort_r()傊偺屇傃弌偟偵曄峏偟傑偟偨丅qsort_r()偺愰尵偼丄include/stdlib.h偵桳傝傑偡丅
			qsort_r(lo, hi_cnt, width, compare, arg); /* 拲堄!![崅埵梫慺偺暲傃]偺愭摢傪巜偟偰偄傞偺偼丄hi偱側偔lo偱偡!! */
//}}2014/11/19曄峏:qsort_r()傪捛壛偟丄qsort()偼qsort_r()傊偺屇傃弌偟偵曄峏偟傑偟偨丅qsort_r()偺愰尵偼丄include/stdlib.h偵桳傝傑偡丅
			/* [掅埵梫慺偺暲傃]傪僜乕僩偟傑偡丅 */
			base = pv, num = lo_cnt;           /* 拲堄!![掅埵梫慺偺暲傃]偺愭摢傪巜偟偰偄傞偺偼丄lo偱側偔pv偱偡!! */
		}
	}
}
#else //PIECE
// * Thu Jan 08 21:00:51 JST 2015 Naoyuki Sawa
// - qsort()偲qsort_r()傪傾僙儞僽儔壔偟傑偟偨丅僐乕僪僒僀僘偑24僶僀僩彫偝偔側傝丄張棟懍搙偑栺4.5%憗偔側傝傑偟偨丅
void qsort(void* base, size_t num, size_t width, int (*compare)(const void*, const void*));
void qsort_r(void* base, size_t num, size_t width, int (*compare)(const void*, const void*, void*), void* arg);
asm("
		.code
		.align		1
		.global		qsort
		.global		qsort_r
qsort:
	;//{{2015/01/09曄峏:Asm斉qsort()傪嵟揔壔偟傑偟偨丅僐乕僪僒僀僘偑偝傜偵8僶僀僩彫偝偔側傝傑偟偨丅
	;//	xsub		%sp, %sp, 4		;//
	;//	xld.w		[%sp+ 0], %r8		;//[%sp+ 0] :=                        NULL
	;//	call		qsort_r			;//qsort_r(base, num, width, compare, NULL)
	;//	xadd		%sp, %sp, 4		;//
	;//	ret
	;//伀2015/01/09曄峏:Asm斉qsort()傪嵟揔壔偟傑偟偨丅僐乕僪僒僀僘偑偝傜偵8僶僀僩彫偝偔側傝傑偟偨丅
	;// * Fri Jan 09 00:00:00 JST 2015 Naoyuki Sawa
	;// - Asm斉qsort()傪嵟揔壔偟傑偟偨丅僐乕僪僒僀僘偑偝傜偵8僶僀僩彫偝偔側傝傑偟偨丅
	;//   qsort()偺張棟偼晄梫偱丄偦偺傑傑qsort_r()傪幚峴偡傟偽ok偱偟偨丅棟桼偼埲壓偺捠傝偱偡丅
	;// - qsort()偑屇傃弌偝傟偨帪偺僗僞僢僋峔憿偼丄埲壓偺捠傝偱偡:
	;//	[%sp + 0] := %pc
	;//	[%sp + 4] := (晄掕抣)
	;//   偙偺傑傑qsort_r()傪幚峴偡傞偲丄(*compare)()偵arg偲偟偰丄(晄掕抣)偑搉偝傟傞偙偲偵側傝傑偡丅
	;//   偟偐偟丄qsort()偐傜屇傃弌偝傟傞(*compare)()偼arg傪庴偗庢傜側偄偺偱丄(晄掕抣)偱峔偄傑偣傫丅
	;//   廬偭偰丄qsort()偺張棟偼晄梫偱丄偦偺傑傑qsort_r()傪幚峴偡傟偽ok偱偡丅
	;// - 尩枾偵偼丄(晄掕抣)偺晹暘偑傾僋僙僗壜擻側RAM偩偲偼曐徹偱偒側偄偺偱偡偑丄尰幚揑偵偼栤戣偁傝傑偣傫丅
	;//   僗僞僢僋偺怺偝偑0偺忬懺偱qsort()傪屇傃弌偡傛偆側応崌偱傕側偗傟偽丄(晄掕抣)偼僗僞僢僋忋偺RAM傪巜偟偰偄傞偐傜偱偡丅
	;//   枩堦忋婰偺傛偆側偙偲傪峴偭偨偲偟偰傕丄P/ECE娐嫬側傜偽柍岠傾僪儗僗偵懳偡傞撉傒弌偟偱堦斒曐岇椺奜偑敪惗偡傞傛偆側偙偲偼柍偄偺偱丄栤戣桳傝傑偣傫丅
		;//** no job **//
	;//}}2015/01/09曄峏:Asm斉qsort()傪嵟揔壔偟傑偟偨丅僐乕僪僒僀僘偑偝傜偵8僶僀僩彫偝偔側傝傑偟偨丅
qsort_r:
		;//[%sp + 0] := %pc
		;//[%sp + 4] := arg
		xld.w		%r9, [%sp + 4]		;//%r9      := arg
		pushn		%r3			;//
		xsub		%sp, %sp, 16		;//
		xld.w		[%sp+ 0], %r9		;//[%sp+ 0] := arg
		xld.w		[%sp+ 4], %r12		;//[%sp+ 4] := pv = base
		xld.w		[%sp+ 8], %r14		;//[%sp+ 8] := width
		xld.w		[%sp+12], %r15		;//[%sp+12] := compare
		;//%r13      := num
		;//[%sp + 0] := arg	仼劉
		;//[%sp + 4] := pv	丂劆
		;//[%sp + 8] := width	丂劆
		;//[%sp +12] := compare	丂劆
		;//[%sp +16] := %r0	丂劆
		;//[%sp +20] := %r1	丂劆
		;//[%sp +24] := %r2	丂劆
		;//[%sp +28] := %r3	丂劆
		;//[%sp +32] := %pc	丂劆
		;//[%sp +36] := arg	劅劊
qsort_r_L10:						;//
		sub		%r13, 2			;//%r13 := (num-2)						劉
		jrult		qsort_r_L60		;//while(  (num-2) >= 0) {					劆
		xld.w		%r0, [%sp+ 4]		;//  %r0  :=      pv						劆
		xld.w		%r1, [%sp+ 8]		;//  %r1  :=           width					劆
		add		%r0, %r1		;//  %r0  := lo = pv + width			!INTERLOCK!	劆
		mltu.w		%r1, %r13		;//  %alr :=           width * (num-2)				劆
		ld.w		%r1, %alr		;//  %r1  :=           width * (num-2)				劆
		add		%r1, %r0		;//  %r1  := hi = pv + width * (num-1)				劏hi偺寁嶼曽朄傪岺晇偟偨丅
		ld.w		%r2, 0			;//  %r2  := lo_cnt = 0
		ld.w		%r3, 0			;//  %r3  := hi_cnt = 0
qsort_r_L20:						;//  do {
		xld.w		%r9, [%sp+12]		;//    %r9  :=            compare
		xld.w		%r13, [%sp+ 4]		;//    %r13 :=                         pv
		xld.w		%r14, [%sp+ 0]		;//    %r14 :=                             arg
		call.d		%r9			;//    %r10 := retval = (*compare)(lo, pv, arg)
		ld.w		%r12, %r0		;//    %r12 :=                  lo		*delay*
		xld.w		%r14, [%sp+ 8]		;//    %r14 :=           width
		cmp		%r10, 0			;//    if(retval <= 0) {
		jrgt		qsort_r_L30		;//      
		add		%r0, %r14		;//      %r0  := lo +=   width
		jp.d		qsort_r_L40		;//      
		add		%r2, 1			;//      %r2  := lo_cnt++			*delay*
qsort_r_L30:						;//    } else
		ld.w		%r12, %r0		;//      %r12 := lo
		ld.w		%r13, %r1		;//      %r13 :=     hi
		xcall.d		xchg			;//      xchg(   lo, hi, width)
		sub		%r1, %r14		;//      %r1  := hi -=   width			*delay*
		add		%r3, 1			;//      %r3  := hi_cnt++
qsort_r_L40:						;//    }
		cmp		%r0, %r1		;//  } while(lo <= hi)
		jrule		qsort_r_L20		;//  
		xld.w		%r12, [%sp+ 4]		;//  %r12 := pv
		xld.w		%r14, [%sp+ 8]		;//  %r14 :=         width
		xcall.d		xchg			;//  xchg(   pv, hi, width)
		ld.w		%r13, %r1		;//  %r13 :=     hi				*delay*
		xld.w		%r14, [%sp+ 8]		;//  %r14 :=               width
		xld.w		%r15, [%sp+12]		;//  %r15 :=                      compare
		cmp		%r2, %r3		;//  if(lo_cnt <= hi_cnt) {
		jrugt		qsort_r_L50		;//    
		xld.w		%r12, [%sp+ 4]		;//    %r12 := pv
		call.d		qsort_r			;//    qsort_r(pv, lo_cnt, width, compare, arg)
		ld.w		%r13, %r2		;//    %r13 :=     lo_cnt			*delay*
		xld.w		[%sp+ 4], %r0		;//    [%sp+ 4] := pv = lo
		jp.d		qsort_r_L10		;//    
		ld.w		%r13, %r3		;//    %r13 := num = hi_cnt			*delay*
qsort_r_L50:						;//  } else {
		ld.w		%r12, %r0		;//    %r12 := lo
		call.d		qsort_r			;//    qsort_r(lo, hi_cnt, width, compare, arg)
		ld.w		%r13, %r3		;//    %r13 :=     hi_cnt			*delay*
		jp.d		qsort_r_L10		;//    
		ld.w		%r13, %r2		;//    %r13 := num = lo_cnt			*delay*
qsort_r_L60:						;//} }
		xadd		%sp, %sp, 16		;//
		popn		%r3			;//
		ret					;//
");
#endif//PIECE

/*****************************************************************************
 *	僸乕僾僜乕僩偲儅乕僕僜乕僩偵偮偄偰(2016/06/10)
 *****************************************************************************/

// * Fri Jun 10 21:42:30 JST 2016 Naoyuki Sawa
// - 婛懚偺hsort()偲msort()傪丄heapsort()偲mergesort()偵柤慜曄峏偟丄/clip/include/stdlib.h偱愰尵偡傞傛偆偵偟傑偟偨丅
//   僸乕僾僜乕僩偲儅乕僕僜乕僩偼昗弨揑側C娭悢偱偼側偄偺偱丄偙傟傑偱偼clipsort.h偱愰尵偟偰偄偨偺偱偡偑丄
//   (ANSI/ISO傗POSIX偱偼側偄傕偺偺)丄FreeBSD偺libc偱偼丄僸乕僾僜乕僩偲儅乕僕僜乕僩偑掕媊偝傟偰偄傞帠偑敾偭偨偐傜偱偡丅
//   FreeBSD偺libc偺娭悢柤偵曧偭偰丄heapsort()偲mergesort()偵柤慜曄峏偟丄/clip/include/stdlib.h偱愰尵偡傞帠偵偟傑偟偨丅
//
//	仩嶲徠帒椏
//	乽FreeBSD Library Functions Manual - QSORT乿(http://www.freebsd.org/cgi/man.cgi?query=qsort&sektion=3&apropos=0&manpath=FreeBSD+10.3-RELEASE+and+Ports)
//	乽FreeBSD 儔僀僽儔儕娭悢儅僯儏傾儖 QSORT(3)乿(http://kaworu.jpn.org/doc/FreeBSD/jman/man3/mergesort.3.php)傛傝堷梡:
//	劆
//	劆	柤徧
//	劆			qsort,heapsort,mergesort - 僜乕僩娭悢
//	劆	儔僀僽儔儕
//	劆			昗弨C儔僀僽儔儕(libc,lc)
//	劆	彂幃
//	劆			#include <stdlib.h>
//	劆			void qsort(void* base, size_t nmemb, size_t size, int (*compar)(const void*, const void*));
//	劆			int heapsort(void* base, size_t nmemb, size_t size, int (*compar)(const void*, const void*));
//	劆			int mergesort(void* base, size_t nmemb, size_t size, int (*compar)(const void*, const void*));
//	劆	夝愢
//	劆			qsort()娭悢偼丄僷乕僥傿僔儑儞岎姺僜乕僩偺廋惓斉丄傛偆偡傞偵僋僀僢僋僜乕僩偱偡丅
//	劆			heapsort()娭悢偼丄慖戰僜乕僩偺廋惓斉偱偡丅
//	劆			mergesort()娭悢偼丄婛偵暲傫偱偄傞売強偺偁傞僨乕僞傪僜乕僩偡傞丄巜悢専嶕偵傛傞儅乕僕僜乕僩偺廋惓斉偱偡丅
//	劆
//	劆			qsort()娭悢偲heapsort()娭悢偼丄base偵傛偭偰弶婜儊儞僶偑巜偝傟偰偄傞nmemb僆僽僕僃僋僩偺攝楍傪僜乕僩偟傑偡丅
//	劆			奺僆僽僕僃僋僩偺僒僀僘偼丄size偱巜掕偟傑偡丅
//	劆			mergesort()傕摨偠傛偆偵摦嶌偟傑偡偑丄size偼``sizeof(void*)/2''傛傝戝偒偔側偗傟偽側傝傑偣傫丅	仼仼仼仼仼摉儔僀僽儔儕偺幚憰偱偼size堷悢偺惂栺偼桳傝傑偣傫丅
//	劆
//	劆			攝楍base偺撪梕偼丄compar偑巜偡斾妑娭悢偵廬偭偰徃弴偱僜乕僩偝傟傑偡丅
//	劆			偙偺娭悢偱偼丄斾妑偡傞僆僽僕僃僋僩傪巜偡丄2偮偺堷悢偑昁梫偱偡丅
//	劆
//	劆			斾妑娭悢偼丄嵟弶偺堷悢偑師偺堷悢傛傝彫偝偄応崌偼0傛傝彫偝偄惍悢丄摍偟偄応崌偼0丄戝偒偄応崌偼0傛傝戝偒偄惍悢傪栠偡昁梫偑偁傝傑偡丅
//	劆
//	劆			qsort()娭悢偲heapsort()娭悢偼晄埨掕偱偡丅
//	劆			偮傑傝2偮偺儊儞僶偑摍偟偄応崌丄僜乕僩嵪傒攝楍撪偱偺弴彉偼晄掕偵側傝傑偡丅
//	劆			mergesort()娭悢偼埨掕偱偡丅
//	劆
//	劆			qsort()娭悢偼丄僷乕僥傿僔儑儞岎姺僜乕僩偺堦庬偱偁傞丄C.A.R. Hoare偺``僋僀僢僋僜乕僩''傾儖僑儕僘儉傪幚憰偟偰偄傑偡丅
//	劆			偲偔偵D.E. Knuth偺傾儖僑儕僘儉Q傪嶲徠偟偰偔偩偝偄丅
//	劆			qsort()偵偼丄暯嬒偱O N lg N偺帪娫偑偐偐傝傑偡丅
//	劆			偙偺幚憰偱偼丄儊僕傾儞慖戰傪巊梡偟偰丄ON**2偲偄偆嵟埆側働乕僗偺摦嶌傪夞旔偟傑偡丅
//	劆
//	劆			heapsort()娭悢偼丄慖戰僜乕僩偺堦庬偱偁傞丄J.W.J. William偺``僸乕僾僜乕僩''傾儖僑儕僘儉傪幚憰偟偰偄傑偡丅
//	劆			偲偔偵D.E. Knuth偺傾儖僑儕僘儉H傪嶲徠偟偰偔偩偝偄丅
//	劆			heapsort()偵偼丄嵟埆偺働乕僗偱O N lg N偺帪娫偑偐偐傝傑偡丅
//	劆			儊儌儕傪傎偲傫偳梋暘偵巊梡偟側偄偲偄偆揰偺傒偑qsort()傛傝桪傟偰偄傑偡丅
//	劆			堦曽丄qsort()偼儊儌儕傪妱傝摉偰傑偣傫偑丄嵞婣傪巊梡偟偰幚憰偝傟偰偄傑偡丅
//	劆
//	劆			mergesort()娭悢偱偼丄nmemb*size僶僀僩偺儊儌儕偑梋暘偵昁梫偲側傝傑偡丅
//	劆			僗儁乕僗偵梋桾偑偁傞応崌偺傒偵巊梡偟偰偔偩偝偄丅
//	劆			mergesort()偼丄婛偵暲傫偱偄傞売強偺偁傞僨乕僞傪埖偆傛偆嵟揔壔偝傟偰偄傑偡丅
//	劆			嵟埆偺働乕僗偺帪娫偼O N lg N偱丄嵟慞偺働乕僗偼O N偱偡丅
//	劆
//	劆			捠忢偼丄heapsort()傛傝mergesort()偺曽偑懍偔丄mergesort()傛傝qsort()偺曽偑崅懍偱偡丅
//	劆			巊梡偱偒傞儊儌儕検傗婛偵暲傫偱偄傞僨乕僞検偵傛傝丄偙偺忬嫷偼曄壔偟傑偡丅
//	劆	栠傝抣
//	劆			qsort()娭悢偼抣傪栠偟傑偣傫丅
//	劆
//	劆			娭悢heapsort()偍傛傃mergesort()偼丄張棟偑惉岟偡傞偲抣0傪曉偟傑偡丅
//	劆			偦偆偱側偄応崌丄抣-1偑曉偝傟丄僌儘乕僶儖曄悢errno偑愝掕偝傟偰僄儔乕傪帵偟傑偡丅
//	劆	僄儔乕
//	劆			heapsort()娭悢偲mergesort()娭悢偼丄埲壓偺傛偆側応崌偵僄儔乕偲側傝傑偡丅													
//	劆			[EINVAL]
//	劆				size堷悢偑0偱偁傞偐丄mergesort()偺size堷悢偑``sizeof(void*)/2''傛傝彫偝偄応崌丅		仼仼仼仼仼摉儔僀僽儔儕偺幚憰偱偼size堷悢偺惂栺偼桳傝傑偣傫丅		劉
//	劆			[ENOMEM]																				劌梫偡傞偵摉幚憰偼忢偵0(惉岟)傪曉偟傑偡丅
//	劆				heapsort()偐mergesort()偑儊儌儕傪妱傝摉偰傜傟側偐偭偨応崌丅				仼仼仼仼仼摉儔僀僽儔儕偺幚憰偱偼張棟傪曉偝偢偵僄儔乕廔椆偟傑偡丅	劊
//	劆	屳姺惈
//	劆			媽僶乕僕儑儞偺qsort()偱偼丄斾妑儖乕僠儞偑qsort(3)傪屇傃弌偡偙偲偼偱偒傑偣傫偱偟偨丅
//	劆			尰嵼偼屇傃弌偣傑偡丅
//	劆	娭楢崁栚
//	劆			sort(1),radixsort(3)
//	劆	婯奿
//	劆			qsort()娭悢偼丄ISO/IEC 9899:1990(``ISO C89'')偵揔崌偟偰偄傑偡丅
//	劆			FreeBSD 10.0 June 4, 1993 FreeBSD 10.0
//	劆
//
// - 撈帺奼挘偲偟偰丄heapsort_r()偲mergesort_r()傕捛壛偟傑偟偨丅
//   偙傟傜偼FreeBSD偺libc偱掕媊偝傟偰偄傑偣傫偑丄昁梫偩偲巚偆偐傜偱偡丅
//   撈帺奼挘偺bsearch_r()傪捛壛偟偨帪偲摨條偱偡丅
//   徻嵶偼丄cliplibc.c偺'Wed May 04 21:28:21 JST 2016'偺僐儊儞僩傪嶲徠偟偰壓偝偄丅

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

#ifndef PIECE	//{{2016/06/10:P/ECE娐嫬偱偼僐乕僪僒僀僘愡栺偺偨傔偵僸乕僾僜乕僩傪柍岠壔偟偰偄傑偡丅桳岠壔偡傞帠傕壜擻偱偡丅}}

// * 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偱偼側偤偐忋弎偺傛偆側戝嵎偵側偭偰偟傑偄傑偟偨丅)
// - 埲壓偺僐乕僪偼丄惓偟偔摦偔偙偲傪妋擣嵪傒偱偡偑丄幚嵺偵巊偆偙偲偼柍偄偲巚偄傑偡丅
//   儕儞僋僒僀僘偑憹偊側偄傛偆偵僐儊儞僩傾僂僩偟偰偁傝傑偡偺偱丄傕偟巊偆応崌偼傾僾儕働乕僔儑儞偵僐僺乕偟偰巊偭偰偔偩偝偄丅
// * Fri Jun 10 21:42:30 JST 2016 Naoyuki Sawa
// - 婛懚偺hsort()偲msort()傪丄heapsort()偲mergesort()偵柤慜曄峏偟丄/clip/include/stdlib.h偱愰尵偡傞傛偆偵偟傑偟偨丅
//   偙傟傑偱偼丄僸乕僾僜乕僩偺幚憰椺偼僐儊儞僩傾僂僩偟偰偄傑偟偨偑丄Win32娐嫬偱偼桳岠壔偟傑偟偨丅
//   偨偩偟丄幚嵺偵昁梫偵側傞帠偼柍偄偲巚偆偺偱丄P/ECE娐嫬偱偼僐乕僪僒僀僘愡栺偺偨傔偵柍岠壔偟偨傑傑偲偟傑偟偨丅
//   崱夞丄僸乕僾僜乕僩傪桳岠壔偟偨棟桼偼丄偁偔傑偱傕Win32娐嫬偱偺僥僗僩偺偨傔偩偗偱偡丅

//{{2016/06/10曄峏:婛懚偺hsort()偲msort()傪丄heapsort()偲mergesort()偵柤慜曄峏偟丄/clip/include/stdlib.h偱愰尵偡傞傛偆偵偟傑偟偨丅
//static void make_heap(unsigned char* base, unsigned char* last, size_t width, int (*compare)(const void*, const void*), unsigned char* parent) {
//伀2016/06/10曄峏:婛懚偺hsort()偲msort()傪丄heapsort()偲mergesort()偵柤慜曄峏偟丄/clip/include/stdlib.h偱愰尵偡傞傛偆偵偟傑偟偨丅
static void make_heap(unsigned char* base, unsigned char* last, size_t width, int (*compare)(const void*, const void*, void*), unsigned char* parent, void* arg) {
//}}2016/06/10曄峏:婛懚偺hsort()偲msort()傪丄heapsort()偲mergesort()偵柤慜曄峏偟丄/clip/include/stdlib.h偱愰尵偡傞傛偆偵偟傑偟偨丅
	unsigned char *child1, *child2;
	/* 嵍偺巕偑桳傟偽... */
	child1 = (base + (parent - base) * 2) + width;
	if(child1 <= last) {
		/* 嵍偺巕偺僣儕乕傪僜乕僩偟傑偡丅 */
//{{2016/06/10曄峏:婛懚偺hsort()偲msort()傪丄heapsort()偲mergesort()偵柤慜曄峏偟丄/clip/include/stdlib.h偱愰尵偡傞傛偆偵偟傑偟偨丅
//		make_heap(base, last, width, compare, child1);
//伀2016/06/10曄峏:婛懚偺hsort()偲msort()傪丄heapsort()偲mergesort()偵柤慜曄峏偟丄/clip/include/stdlib.h偱愰尵偡傞傛偆偵偟傑偟偨丅
		make_heap(base, last, width, compare, child1, arg);
//}}2016/06/10曄峏:婛懚偺hsort()偲msort()傪丄heapsort()偲mergesort()偵柤慜曄峏偟丄/clip/include/stdlib.h偱愰尵偡傞傛偆偵偟傑偟偨丅
		/* 塃偺巕偑桳傟偽... */
		child2 = child1 + width;
		if(child2 <= last) {
			/* 塃偺巕偺僣儕乕傪僜乕僩偟傑偡丅 */
//{{2016/06/10曄峏:婛懚偺hsort()偲msort()傪丄heapsort()偲mergesort()偵柤慜曄峏偟丄/clip/include/stdlib.h偱愰尵偡傞傛偆偵偟傑偟偨丅
//			make_heap(base, last, width, compare, child2);
//伀2016/06/10曄峏:婛懚偺hsort()偲msort()傪丄heapsort()偲mergesort()偵柤慜曄峏偟丄/clip/include/stdlib.h偱愰尵偡傞傛偆偵偟傑偟偨丅
			make_heap(base, last, width, compare, child2, arg);
//}}2016/06/10曄峏:婛懚偺hsort()偲msort()傪丄heapsort()偲mergesort()偵柤慜曄峏偟丄/clip/include/stdlib.h偱愰尵偡傞傛偆偵偟傑偟偨丅
			/* child1偑戝偒偄曽偺巕傪巜偡傛偆偵偟傑偡丅 */
//{{2016/06/10曄峏:婛懚偺hsort()偲msort()傪丄heapsort()偲mergesort()偵柤慜曄峏偟丄/clip/include/stdlib.h偱愰尵偡傞傛偆偵偟傑偟偨丅
//			if((*compare)(child1, child2) < 0) {
//伀2016/06/10曄峏:婛懚偺hsort()偲msort()傪丄heapsort()偲mergesort()偵柤慜曄峏偟丄/clip/include/stdlib.h偱愰尵偡傞傛偆偵偟傑偟偨丅
			if((*compare)(child1, child2, arg) < 0) {
//}}2016/06/10曄峏:婛懚偺hsort()偲msort()傪丄heapsort()偲mergesort()偵柤慜曄峏偟丄/clip/include/stdlib.h偱愰尵偡傞傛偆偵偟傑偟偨丅
				child1 = child2;
			}
		}
		/* 戝偒偄曽偺巕偑恊傛傝傕戝偒偗傟偽... */
//{{2016/06/10曄峏:婛懚偺hsort()偲msort()傪丄heapsort()偲mergesort()偵柤慜曄峏偟丄/clip/include/stdlib.h偱愰尵偡傞傛偆偵偟傑偟偨丅
//		if((*compare)(parent, child1) < 0) {
//伀2016/06/10曄峏:婛懚偺hsort()偲msort()傪丄heapsort()偲mergesort()偵柤慜曄峏偟丄/clip/include/stdlib.h偱愰尵偡傞傛偆偵偟傑偟偨丅
		if((*compare)(parent, child1, arg) < 0) {
//}}2016/06/10曄峏:婛懚偺hsort()偲msort()傪丄heapsort()偲mergesort()偵柤慜曄峏偟丄/clip/include/stdlib.h偱愰尵偡傞傛偆偵偟傑偟偨丅
			/* 戝偒偄曽偺巕偲恊傪擖傟懼偊傑偡丅 */
			xchg(parent, child1, width);
			//make_heap(base, last, width, compare, child1);
			//仺巕偺僣儕乕偺僜乕僩偼師夞偵峴偆偺偱晄梫偱偡丅
		}
	}
}

//{{2016/06/10曄峏:婛懚偺hsort()偲msort()傪丄heapsort()偲mergesort()偵柤慜曄峏偟丄/clip/include/stdlib.h偱愰尵偡傞傛偆偵偟傑偟偨丅
//void hsort(void* _base, size_t num, size_t width, int (*compare)(const void*, const void*)) {
//伀2016/06/10曄峏:婛懚偺hsort()偲msort()傪丄heapsort()偲mergesort()偵柤慜曄峏偟丄/clip/include/stdlib.h偱愰尵偡傞傛偆偵偟傑偟偨丅
int heapsort(void* _base, size_t num, size_t width, int (*compare)(const void*, const void*)) {	//FreeBSD 10.0 June 4, 1993 FreeBSD 10.0
	return heapsort_r(_base, num, width, (int (*)(const void*, const void*, void*))compare, NULL);
}
int heapsort_r(void* _base, size_t num, size_t width, int (*compare)(const void*, const void*, void*), void* arg) {	//撈帺奼挘
//}}2016/06/10曄峏:婛懚偺hsort()偲msort()傪丄heapsort()偲mergesort()偵柤慜曄峏偟丄/clip/include/stdlib.h偱愰尵偡傞傛偆偵偟傑偟偨丅
	unsigned char* base = _base;
	unsigned char* last = base + (width * (num - 1));
	while(base < last) {
		/* 僣儕乕慡懱傪崀弴偵僜乕僩偟傑偡丅 */
//{{2016/06/10曄峏:婛懚偺hsort()偲msort()傪丄heapsort()偲mergesort()偵柤慜曄峏偟丄/clip/include/stdlib.h偱愰尵偡傞傛偆偵偟傑偟偨丅
//		make_heap(base, last, width, compare, base);
//伀2016/06/10曄峏:婛懚偺hsort()偲msort()傪丄heapsort()偲mergesort()偵柤慜曄峏偟丄/clip/include/stdlib.h偱愰尵偡傞傛偆偵偟傑偟偨丅
		make_heap(base, last, width, compare, base, arg);
//}}2016/06/10曄峏:婛懚偺hsort()偲msort()傪丄heapsort()偲mergesort()偵柤慜曄峏偟丄/clip/include/stdlib.h偱愰尵偡傞傛偆偵偟傑偟偨丅
		/* 嵟戝梫慺傪僣儕乕偺枛旜偵愗傝棧偟傑偡丅 */
		xchg(base, last, width);
		last -= width;
	}
//{{2016/06/10捛壛:婛懚偺hsort()偲msort()傪丄heapsort()偲mergesort()偵柤慜曄峏偟丄/clip/include/stdlib.h偱愰尵偡傞傛偆偵偟傑偟偨丅
	return 0;
//}}2016/06/10捛壛:婛懚偺hsort()偲msort()傪丄heapsort()偲mergesort()偵柤慜曄峏偟丄/clip/include/stdlib.h偱愰尵偡傞傛偆偵偟傑偟偨丅
}

#endif//PIECE	//{{2016/06/10:P/ECE娐嫬偱偼僐乕僪僒僀僘愡栺偺偨傔偵僸乕僾僜乕僩傪柍岠壔偟偰偄傑偡丅桳岠壔偡傞帠傕壜擻偱偡丅}}

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

/* * 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)
 */

#if 0
//{{2016/06/10曄峏:婛懚偺hsort()偲msort()傪丄heapsort()偲mergesort()偵柤慜曄峏偟丄/clip/include/stdlib.h偱愰尵偡傞傛偆偵偟傑偟偨丅
//static void mergeseqs(size_t size, const unsigned char* from, unsigned char* to, size_t num, size_t width, int (*compare)(const void*, const void*)) {
//伀2016/06/10曄峏:婛懚偺hsort()偲msort()傪丄heapsort()偲mergesort()偵柤慜曄峏偟丄/clip/include/stdlib.h偱愰尵偡傞傛偆偵偟傑偟偨丅
//仩慺捈側幚憰
static void mergeseqs(size_t size, const unsigned char* from, unsigned char* to, size_t num, size_t width, int (*compare)(const void*, const void*, void*), void* arg) {
//}}2016/06/10曄峏:婛懚偺hsort()偲msort()傪丄heapsort()偲mergesort()偵柤慜曄峏偟丄/clip/include/stdlib.h偱愰尵偡傞傛偆偵偟傑偟偨丅
	size_t i, j, k, iend, jend;
	for(jend = 0; jend < num; /** no job **/) {
		i    = k = jend;
		iend = j = i + size;
		jend     = j + size;
		if(iend > num) {
			iend = num;
		}
		if(jend > num) {
			jend = num;
		}
		while((i < iend) && (j < jend)) {
//{{2016/06/10曄峏:婛懚偺hsort()偲msort()傪丄heapsort()偲mergesort()偵柤慜曄峏偟丄/clip/include/stdlib.h偱愰尵偡傞傛偆偵偟傑偟偨丅
//			if((*compare)(&from[i * width], &from[j * width]) <= 0) {
//伀2016/06/10曄峏:婛懚偺hsort()偲msort()傪丄heapsort()偲mergesort()偵柤慜曄峏偟丄/clip/include/stdlib.h偱愰尵偡傞傛偆偵偟傑偟偨丅
			if((*compare)(&from[i * width], &from[j * width], arg) <= 0) {
//}}2016/06/10曄峏:婛懚偺hsort()偲msort()傪丄heapsort()偲mergesort()偵柤慜曄峏偟丄/clip/include/stdlib.h偱愰尵偡傞傛偆偵偟傑偟偨丅
				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);
		}
	}
}
//{{2016/06/10曄峏:婛懚偺hsort()偲msort()傪丄heapsort()偲mergesort()偵柤慜曄峏偟丄/clip/include/stdlib.h偱愰尵偡傞傛偆偵偟傑偟偨丅
//void msort(void* base, size_t num, size_t width, int (*compare)(const void*, const void*)) {
//伀2016/06/10曄峏:婛懚偺hsort()偲msort()傪丄heapsort()偲mergesort()偵柤慜曄峏偟丄/clip/include/stdlib.h偱愰尵偡傞傛偆偵偟傑偟偨丅
int mergesort(void* base, size_t num, size_t width, int (*compare)(const void*, const void*)) {	//FreeBSD 10.0 June 4, 1993 FreeBSD 10.0
	return mergesort_r(base, num, width, (int (*)(const void*, const void*, void*))compare, NULL);
}
int mergesort_r(void* base, size_t num, size_t width, int (*compare)(const void*, const void*, void*), void* arg) {	//撈帺奼挘
//}}2016/06/10曄峏:婛懚偺hsort()偲msort()傪丄heapsort()偲mergesort()偵柤慜曄峏偟丄/clip/include/stdlib.h偱愰尵偡傞傛偆偵偟傑偟偨丅
	void *a = base, *b;
	size_t seqsize;
	b = malloc(num * width);
	if(!b) { DIE(); }
	for(seqsize = 1; seqsize < num; /** no job **/) {
//{{2016/06/10曄峏:婛懚偺hsort()偲msort()傪丄heapsort()偲mergesort()偵柤慜曄峏偟丄/clip/include/stdlib.h偱愰尵偡傞傛偆偵偟傑偟偨丅
//		mergeseqs(seqsize, a, b, num, width, compare);
//伀2016/06/10曄峏:婛懚偺hsort()偲msort()傪丄heapsort()偲mergesort()偵柤慜曄峏偟丄/clip/include/stdlib.h偱愰尵偡傞傛偆偵偟傑偟偨丅
		mergeseqs(seqsize, a, b, num, width, compare, arg);
//}}2016/06/10曄峏:婛懚偺hsort()偲msort()傪丄heapsort()偲mergesort()偵柤慜曄峏偟丄/clip/include/stdlib.h偱愰尵偡傞傛偆偵偟傑偟偨丅
		seqsize *= 2;
//伀2016/06/10曄峏:婛懚偺hsort()偲msort()傪丄heapsort()偲mergesort()偵柤慜曄峏偟丄/clip/include/stdlib.h偱愰尵偡傞傛偆偵偟傑偟偨丅
//		mergeseqs(seqsize, b, a, num, width, compare);
//伀2016/06/10曄峏:婛懚偺hsort()偲msort()傪丄heapsort()偲mergesort()偵柤慜曄峏偟丄/clip/include/stdlib.h偱愰尵偡傞傛偆偵偟傑偟偨丅
		mergeseqs(seqsize, b, a, num, width, compare, arg);
//伀2016/06/10曄峏:婛懚偺hsort()偲msort()傪丄heapsort()偲mergesort()偵柤慜曄峏偟丄/clip/include/stdlib.h偱愰尵偡傞傛偆偵偟傑偟偨丅
		seqsize *= 2;
	}
	free(b);
//{{2016/06/10捛壛:婛懚偺hsort()偲msort()傪丄heapsort()偲mergesort()偵柤慜曄峏偟丄/clip/include/stdlib.h偱愰尵偡傞傛偆偵偟傑偟偨丅
	return 0;
//}}2016/06/10捛壛:婛懚偺hsort()偲msort()傪丄heapsort()偲mergesort()偵柤慜曄峏偟丄/clip/include/stdlib.h偱愰尵偡傞傛偆偵偟傑偟偨丅
}
#else	//伀{{2016/06/10曄峏:傾僙儞僽儔壔偟傑偟偨丅僐乕僪僒僀僘偑72僶僀僩彫偝偔側傝傑偟偨丅懍搙傕懡彮憗偔側偭偨偲巚偄傑偡偑丄尦乆malloc/free傪巊偭偰偄傞偺偱慡懱偲偟偰偺懍搙偼偁傑傝曄傢傜側偄偲巚偄傑偡丅}}
//仩傾僙儞僽儔壔偡傞偨傔偺弨旛偲偟偰曄峏偟偨幚憰丅
// - '慺捈側幚憰'偱偼僀儞僨僋僗儀乕僗偱偁偭偨張棟傪丄'傾僙儞僽儔壔偡傞偨傔偺弨旛偲偟偰曄峏偟偨幚憰'偱偼億僀儞僞儀乕僗偺張棟偵曄峏偟傑偟偨丅
//   曄峏偟偨棟桼偼丄傾僙儞僽儔壔偡傞帪偵丄昁梫側儗僕僗僞悢傪尭傜偡偨傔偺弨旛偱偡丅
// - '傾僙儞僽儔壔偡傞偨傔偺弨旛偲偟偰曄峏偟偨幚憰'傕丄傾儖僑儕僘儉帺懱偼'慺捈側幚憰'偲摨偠偱偡丅
//   '傾僙儞僽儔壔偡傞偨傔偺弨旛偲偟偰曄峏偟偨幚憰'偺僐乕僪偼丄撉傫偱敾傝偯傜偄偲巚偆偺偱丄傾儖僑儕僘儉帺懱偼'慺捈側幚憰'傪嶲徠偟偰壓偝偄丅
#ifndef PIECE
static void mergeseqs(size_t size, const unsigned char* from, unsigned char* to, size_t num, size_t width, int (*compare)(const void*, const void*, void*), void* arg) {
	const int from_to = to - from;							//偙傟埲崀丄to偼晄梫丅		偙傟埲崀丄from_to偼曄壔偟側偄丅		from_to偼儊儌儕偵抲偗丅
	const unsigned char *from_num, *from_i, *from_iend, *from_j, *from_jend;
	unsigned char* to_k;
	size *= width;									//				偙傟埲崀丄size偼曄壔偟側偄丅		size偼儊儌儕偵抲偗丅
	num  *= width;									//				偙傟埲崀丄num偼曄壔偟側偄丅
	from_num = &from[num];								//偙傟埲崀丄num偼晄梫丅		偙傟埲崀丄from_num偼曄壔偟側偄丅	from_num偼儊儌儕偵抲偄偰傕椙偄偑丄儗僕僗僞偑堦偮梋偭偨偺偱丄from_num傪儗僕僗僞偵抲偔帠偵偟偨丅儊儌儕偵抲偄偰傕椙偄曄悢偺偆偪丄from_num傪儗僕僗僞偵抲偔偺偑堦斣岠壥偑崅偄偲巚偆偐傜偱偡丅
	for(from_jend = from; from_jend < from_num; /** no job **/) {			//偙傟埲崀丄from偼晄梫丅
		from_i    = from_jend;							//													from_i偼儗僕僗僞偵抲偗丅
		from_iend = from_i + size;
		from_j    = from_iend;							//													from_j偼儗僕僗僞偵抲偗丅
		from_jend = from_j + size;						//偙傟埲崀丄size偼晄梫丅
		if(from_iend > from_num) {
			from_iend = from_num;						//				偙傟埲崀丄from_iend偼曄壔偟側偄丅	from_iend偼儊儌儕偵抲偗丅
		}
		if(from_jend > from_num) {
			from_jend = from_num;						//				偙傟埲崀丄from_jend偼曄壔偟側偄丅	from_jend偼儊儌儕偵抲偗丅
		}
		to_k = (unsigned char*)(from_i + from_to);				//													to_k偼儗僕僗僞偵抲偗丅
		while((from_i < from_iend) && (from_j < from_jend)) {
			if((*compare)(from_i, from_j, arg) <= 0) {
				memcpy(to_k, from_i, width);
				from_i += width;
			} else {
				memcpy(to_k, from_j, width);
				from_j += width;
			}
			to_k += width;
		}
		if(from_iend > from_i) {
			memcpy(to_k, from_i, from_iend - from_i);
		}
		if(from_jend > from_j) {
			memcpy(to_k, from_j, from_jend - from_j);
		}
	}
}
int mergesort(void* base, size_t num, size_t width, int (*compare)(const void*, const void*)) {	//FreeBSD 10.0 June 4, 1993 FreeBSD 10.0
	return mergesort_r(base, num, width, (int (*)(const void*, const void*, void*))compare, NULL);
}
int mergesort_r(void* base, size_t num, size_t width, int (*compare)(const void*, const void*, void*), void* arg) {	//撈帺奼挘
	void *a = base, *b;
	size_t seqsize;
	b = malloc(num * width);
	if(!b) { DIE(); }
	for(seqsize = 1; seqsize < num; /** no job **/) {
		mergeseqs(seqsize, a, b, num, width, compare, arg);
		seqsize *= 2;
		mergeseqs(seqsize, b, a, num, width, compare, arg);
		seqsize *= 2;
	}
	free(b);
	return 0;
}
#else //PIECE
/*static*/ void mergeseqs(size_t size, const unsigned char* from, unsigned char* to, size_t num, size_t width, int (*compare)(const void*, const void*, void*), void* arg);
int mergesort(void* base, size_t num, size_t width, int (*compare)(const void*, const void*));	//FreeBSD 10.0 June 4, 1993 FreeBSD 10.0
int mergesort_r(void* base, size_t num, size_t width, int (*compare)(const void*, const void*, void*), void* arg);	//撈帺奼挘
asm("
		.global		mergesort
		.global		mergesort_r
mergesort:
		;//[%sp+0] := retp
		;//[%sp+4] := (arg = 晄掕抣)
mergesort_r:
		pushn		%r3
		xsub		%sp, %sp, 12
		;//%r0      := (a)
		;//%r1      := (num)
		;//%r2      := (b)
		;//%r3      := (seqsize)
		;//%r12     := base
		;//%r13     := num
		;//%r14     := width
		;//%r15     := compare
		;//[%sp+0]  := (width)		劉
		;//[%sp+4]  := (compare)	劌mergeseqs()傊偺戞5,戞6,戞7堷悢偵側傝傑偡丅
		;//[%sp+8]  := (arg)		劊
		;//[%sp+12] := %r0
		;//[%sp+16] := %r1
		;//[%sp+20] := %r2
		;//[%sp+24] := %r3
		;//[%sp+28] := retp
		;//[%sp+32] := arg
		ld.w		%r0, %r12			;//%r0     := a = base
		ld.w		%r1, %r13			;//%r1     := num
		xld.w		%r9, [%sp+32]			;//%r9     := arg
		xld.w		[%sp+0], %r14			;//[%sp+0] := width
		xld.w		[%sp+4], %r15			;//[%sp+4] := compare
		xld.w		[%sp+8], %r9			;//[%sp+8] := arg
		mlt.w		%r13, %r14			;//%alr    :=            num * width
		xcall.d		malloc				;//%r10    := b = malloc(num * width)
		ld.w		%r12, %alr			;//%r12    :=            num * width				*delay*
		cmp		%r10, 0				;//if(       !b) { DIE() }
		jreq		mergesort_r_DIE			;//
		ld.w		%r2, %r10			;//%r2     := b
		ld.w		%r3, 1				;//%r3     :=  seqsize = 1
		;//- - - - - - - - - - - - - - - - - - - - - - -;//
mergesort_r_LOOP:						;//for(;;) {
		cmp		%r3, %r1			;//  if(seqsize >= num) { goto EXIT }
		jrge		mergesort_r_EXIT		;//  
		ld.w		%r12, %r3			;//  %r12 :=   seqsize
		ld.w		%r13, %r0			;//  %r13 :=            a
		ld.w		%r14, %r2			;//  %r14 :=               b
		call.d		mergeseqs			;//  mergeseqs(seqsize, a, b, num, width, compare, arg)
		ld.w		%r15, %r1			;//  %r15 :=                  num				*delay*
		add		%r3, %r3			;//  %r3  :=   seqsize *= 2
		ld.w		%r12, %r3			;//  %r12 :=   seqsize
		ld.w		%r13, %r2			;//  %r13 :=            b
		ld.w		%r14, %r0			;//  %r14 :=               a
		call.d		mergeseqs			;//  mergeseqs(seqsize, b, a, num, width, compare, arg)
		ld.w		%r15, %r1			;//  %r15 :=                  num				*delay*
		jp.d		mergesort_r_LOOP		;//}
		add		%r3, %r3			;//  %r3  :=   seqsize *= 2					*delay*
mergesort_r_EXIT:						;//
		;//- - - - - - - - - - - - - - - - - - - - - - -;//
		xcall.d		free				;//free(     b)
		ld.w		%r12, %r2			;//%r12   := b							*delay*
		xadd		%sp, %sp, 12			;//
		popn		%r3				;//
		ret.d						;//return    0
		ld.w		%r10, 0				;//%r10   := 0							*delay*
		;//---------------------------------------------;//
mergeseqs:
		pushn		%r3
		xsub		%sp, %sp, 16
		;//%r0      := (from_num)
		;//%r1      := (from_i)
		;//%r2      := (from_j)
		;//%r3      := (to_k)
		;//%r12     := size
		;//%r13     := from	劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劉
		;//%r14     := to													劆
		;//%r15     := num													劆
		;//[%sp+0]  := (from_to)												劆
		;//[%sp+4]  := (size)													劆
		;//[%sp+8]  := (from_iend)												劆
		;//[%sp+12] := (from_jend)												劆
		;//[%sp+16] := %r0													劆
		;//[%sp+20] := %r1													劆
		;//[%sp+24] := %r2													劆
		;//[%sp+28] := %r3													劆
		;//[%sp+32] := retp													劆
		;//[%sp+36] := width													劆
		;//[%sp+40] := compare													劆
		;//[%sp+44] := arg													劆
		xld.w		%r9, [%sp+36]			;//%r9      :=         width						劆
		sub		%r14, %r13			;//%r14     := from_to = to - from					劆
		xld.w		[%sp+0], %r14			;//[%sp+0]  := from_to							劆
		mlt.w		%r12, %r9			;//%alr     := size *= width						劆
		ld.w		%r12, %alr			;//%r12     := size							劆
		xld.w		[%sp+4], %r12			;//[%sp+4]  := size							劆
		mlt.w		%r15, %r9			;//%alr     :=                  num *= width				劆
		ld.w		%r0, %alr			;//%r0      :=                  num					劆
		add		%r0, %r13			;//%r0      := from_num = &from[num]					劆
		;//- - - - - - - - - - - - - - - - - - - - - - -;//%r13     := from_jend = from						劆
mergeseqs_LOOP1:						;//for(;;) {								劆
		cmp		%r13, %r0			;//  if(from_jend >= from_num) { goto EXIT1 }	仼劅劅劅劅劅劅劅劅劅劅劅劎
		jruge		mergeseqs_EXIT1			;//  									劆
		xld.w		%r3, [%sp+0]			;//  %r3      :=                 from_to				劆
		xld.w		%r4, [%sp+4]			;//  %r4      :=                      size				劆
		ld.w		%r1, %r13			;//  %r1      := from_i    = from_jend					劆
		ld.w		%r5, %r1			;//  %r5      :=             from_i					劆
		add		%r5, %r4			;//  %r5      := from_iend = from_i + size				劆
		ld.w		%r2, %r5			;//  %r2      := from_j    = from_iend					劆
		ld.w		%r6, %r2			;//  %r6      :=             from_j					劆
		add		%r6, %r4			;//  %r6      := from_jend = from_j + size				劆
		cmp		%r5, %r0			;//  if(from_iend > from_num) {						劆
		jrule.d		3				;//    									劆
		 cmp		%r6, %r0			;//   仼劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劉			劆	*delay*
		 ld.w		%r5, %r0			;//    %r5      := from_iend = from_num }	劆			劆
	;//	cmp		%r6, %r0			;//  if(from_jend > from_num) {		劅劅劅劅劊			劆
		jrule.d		3				;//    									劆
		 add		%r3, %r1			;//  %r3      := to_k = from_i + from_to				劆	*delay*
		 ld.w		%r6, %r0			;//    %r6      := from_jend = from_num }				劆
		xld.w		[%sp+8], %r5			;//  [%sp+8]  := from_iend						劆
		xld.w		[%sp+12], %r6			;//  [%sp+12] := from_jend						劆
		;//- - - - - - - - - - - - - - - - - - - - - - -;//									劆
mergeseqs_LOOP2:						;//  for(;;) {								劆
		xld.w		%r14, [%sp+8]			;//    %r14     := from_iend	劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劉	劆
		xld.w		%r9, [%sp+12]			;//    %r9      := from_jend					劆	劆	*anti-interlock*
		cmp		%r1, %r14			;//    if(from_i >= from_iend) { goto EXIT2 }			劆	劆
		jruge		mergeseqs_EXIT2			;//    								劆	劆
		cmp		%r2, %r9			;//    if(from_j >= from_jend) { goto EXIT2 }			劆	劆
		jruge		mergeseqs_EXIT2			;//    								劆	劆
		xld.w		%r9, [%sp+40]			;//    %r9      :=   compare					劆	劆
		xld.w		%r14, [%sp+44]			;//    %r14     :=                            arg		劆	劆
		ld.w		%r12, %r1			;//    %r12     :=            from_i				劆	劆
		call.d		%r9				;//    %r10     := (*compare)(from_i, from_j, arg)		劆	劆
		ld.w		%r13, %r2			;//    %r13     :=                    from_j			劆	劆	*delay*
		xld.w		%r14, [%sp+36]			;//    %r14     :=                 width			劆	劆
		cmp		%r10, 0				;//    if(         (*compare)(from_i, from_j, arg) <= 0) {	劆	劆
		jrgt.d		5		;//劅劉		;//      							劆	劆
		 ld.w		%r12, %r3	;//丂劆		;//    %r12     := to_k						劆	劆	*delay*
		 ld.w		%r13, %r1	;//丂劆		;//      %r13     :=     from_i		劅劅劅劅劅劅劅劅劉	劆	劆
		 jp.d		4		;//丂劆	;//劅劉	;//    } else {						劆	劆	劆
		 add		%r1, %r14	;//丂劆	;//丂劆	;//      %r1      :=     from_i += width		劆	劆	劆	*delay*
		ld.w		%r13, %r2	;//仼劊	;//丂劆	;//      %r13     :=     from_j		劅劅劅劅劅劅劅劅劎	劆	劆
		add		%r2, %r14		;//丂劆	;//      %r2      :=     from_j += width		劆	劆	劆
		call.d		mergeseqs_MEMCPY	;//仼劊	;//      memcpy(   to_k, from_?,   width)	仼劅劅劅劊	劆	劆
		add		%r3, %r14			;//    %r3      := to_k         += width			劆	劆	*delay*
		jp		mergeseqs_LOOP2			;//  }								劆	劆	*anti-interlock*
mergeseqs_EXIT2:						;//  								劆	劆
		;//- - - - - - - - - - - - - - - - - - - - - - -;//								劆	劆
	;//	xld.w		%r14, [%sp+8]			;//  %r14     :=                 from_iend	仼劅劅劅劅劅劅劅劊	劆
		sub		%r14, %r1			;//  %r14     :=                 from_iend - from_i			劆
		jrule		4				;//  if(                         from_iend > from_i) {			劆
		 ld.w		%r12, %r3			;//    %r12     := to_k							劆
		 call.d		mergeseqs_MEMCPY		;//    memcpy(     to_k, from_i, from_iend - from_i) }			劆
		 ld.w		%r13, %r1			;//    %r13     :=       from_i						劆	*delay*
		xld.w		%r14, [%sp+12]			;//  %r14     :=                 from_jend				劆
		sub		%r14, %r2			;//  if(                         from_jend - from_j) {			劆	!INTERLOCK!
		jrule		4				;//  if(                         from_jend > from_j) {			劆
		 ld.w		%r12, %r3			;//    %r12     := to_k							劆
		 call.d		mergeseqs_MEMCPY		;//    memcpy(     to_k, from_j, from_jend - from_j) }			劆
		 ld.w		%r13, %r2			;//    %r13     :=       from_j						劆	*delay*
		xld.w		%r13, [%sp+12]			;//  %r13     := from_jend	劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劊
		jp		mergeseqs_LOOP1			;//}
mergeseqs_EXIT1:						;//
		;//- - - - - - - - - - - - - - - - - - - - - - -;//
		xadd		%sp, %sp, 16			;//
		popn		%r3				;//
		ret						;//
		;//- - - - - - - - - - - - - - - - - - - - - - -;//
mergeseqs_MEMCPY:						;//
		xjp		memcpy				;//摉娭悢偵偼memcpy屇傃弌偟偑3偐強桳傞偺偱丄偦傟傜偺3偐強傪1柦椷(jp)偵偟偰丄偙偙偵捛壛偺2柦椷(xjp)傪愝偗傞曽偑丄慡懱偲偟偰偼1柦椷偺愡栺偵側傞丅
");
static void __attribute__((noreturn,unused))/*asm僽儘僢僋偐傜嶲徠*/ mergesort_r_DIE() { DIE(); }
#endif//PIECE
#endif

/*****************************************************************************
 *	僥僗僩僗僀乕僩
 *****************************************************************************/
#if 0
static void test_subr(void (*sort_r)(void*, size_t, size_t, int (*)(const void*,const void*, void*), void*));	//慜曽嶲徠
//2016/06/10尰嵼丄Win32娐嫬偲P/ECE娐嫬偱惓忢偵摦嶌偡傞帠傪妋擣偟傑偟偨丅
void test() {
	int i;
	for(i = 0; i < 100; i++) { test_subr(qsort_r); }											//qsort_r偺僥僗僩
  #ifndef PIECE	//{{2016/06/10:P/ECE娐嫬偱偼僐乕僪僒僀僘愡栺偺偨傔偵僸乕僾僜乕僩傪柍岠壔偟偰偄傑偡丅桳岠壔偡傞帠傕壜擻偱偡丅}}
	for(i = 0; i < 100; i++) { test_subr((void (*)(void*, size_t, size_t, int (*)(const void*,const void*, void*), void*))heapsort_r); }	//heapsort_r偺僥僗僩
  #endif//PIECE	//{{2016/06/10:P/ECE娐嫬偱偼僐乕僪僒僀僘愡栺偺偨傔偵僸乕僾僜乕僩傪柍岠壔偟偰偄傑偡丅桳岠壔偡傞帠傕壜擻偱偡丅}}
	for(i = 0; i < 100; i++) { test_subr((void (*)(void*, size_t, size_t, int (*)(const void*,const void*, void*), void*))mergesort_r); }	//mergesort_r偺僥僗僩
	puts("ok");
}
static int compar(const void* _x, const void* _y, void* arg) {
	const char* x = _x;
	const char* y = _y;
	int offset = (int)arg;
	return x[offset] - y[offset];
}
static void test_subr(void (*sort_r)(void*, size_t, size_t, int (*)(const void*,const void*, void*), void*)) {
    #define N 127
	char data[N][2+1/*nul*/];
	int i;
	//儔儞僟儉側暥帤楍("0A"乣"9Z")傪嶌惉偡傞丅
	for(i = 0; i < N; i++) {
		data[i][0] = RND32_RANGE(seed, '0', '9' + 1);
		data[i][1] = RND32_RANGE(seed, 'A', 'Z' + 1);
		data[i][2] = '\0';
	}
	//愭偵丄暥帤楍偺2暥帤栚偱僜乕僩偡傞丅
	(*sort_r)(&data[0][0], N, 2+1/*nul*/, compar, (void*)1);
	//師偵丄暥帤楍偺1暥帤栚偱僜乕僩偡傞丅
	(*sort_r)(&data[0][0], N, 2+1/*nul*/, compar, (void*)0);
	//寢壥傪妋擣偡傞丅
	for(i = 0; i < N; i++) {
	    //	printf("%s\n", data[i]);
		if(i && (strncmp(data[i - 1], data[i], 1) > 0)) { DIE(); }										//偳偺僜乕僩偱傕丄屻偱僜乕僩偟偨曽(1暥帤栚)偼徃弴偵側偭偰偄傞偼偢丅
		if(i && ( strcmp(data[i - 1], data[i]   ) > 0)) { if((void*)sort_r == (void*)mergesort_r) { DIE(); } /*else { printf("*"); }*/ }	//mergesort_r偼埨掕僜乕僩側偺偱愭偵僜乕僩偟偨曽(2暥帤栚)偼堐帩偝傟偰偄傞偼偢丅qsort_r,heapsort_r偼晄埨掕僜乕僩側偺偱愭偵僜乕僩偟偨曽(2暥帤栚)偼晄掕偱偁傞丅
	}
    #undef  N
}
#endif

/****************************************************************************
 *	懍搙寁應寢壥(2016/06/11)
 ****************************************************************************/
// * Sat Jun 11 20:47:59 JST 2016 Naoyuki Sawa
// - clipsort.c偺堦斣壓偵丄乽懍搙寁應寢壥(2016/06/11)乿傪捛婰偟傑偟偨丅
//   Win10(x64)偲P/ECE偱丄奺娭悢偺懍搙傪寁應偟偨寢壥偲丄峫嶡偱偡丅
//   {{寁應僾儘僌儔儉:偙偙偐傜
#if 0
#define N 32768
static uint8_t data[N][2];
static int compar(const void* _x, const void* _y, void* arg) {
	int offset = (int)arg;
	int x = ((uint8_t*)_x)[offset];
	int y = ((uint8_t*)_y)[offset];
	if(x < y) { return -1; }
	if(x > y) { return  1; }
	return 0;
}
static void test(void (*sort)(void*,size_t,size_t,int (*)(const void*,const void*,void*), void*)) {
	int i, t, seed = 0;
	for(i = 0; i < N; i++) {
		data[i][0] = RND8(seed);
		data[i][1] = RND8(seed);
	}
    #ifdef  PIECE
	t = pceTimerGetCount();
    #else //PIECE
	t = GetTickCount();
    #endif//PIECE
	for(i = 0; i < 3; i++) {
		(*sort)(data, N, 2, compar, (void*)0);
		(*sort)(data, N, 2, compar, (void*)1);
	}
    #ifdef  PIECE
	t = pceTimerGetCount() - t;
	die("%d", t);
    #else //PIECE
	t = GetTickCount() - t;
	printf("%d\n", t);
	getch();
    #endif//PIECE
}
int app_main(int argc, char* argv[]) {
	test(qsort_r);
   //	test(heapsort_r);
   //	test(qsort_r);
	return 0;
}
#endif
//   }}寁應僾儘僌儔儉:偙偙傑偱
// - 仩寢壥
//   test(qsort_r)偺寢壥:
//   丒Core i7-4500U	   78[ms]	VC++6.0,儕儕乕僗僺儖僪
//   丒P/ECE		43407[ms]	C尵岅斉qsort_r()
//   丒P/ECE		41404[ms]	傾僙儞僽儔斉qsort_r()
//   test(heapsort_r)偺寢壥:
//   丒Core i7-4500U	45953[ms]	VC++6.0,儕儕乕僗僺儖僪
//   丒P/ECE		(枹懳墳)
//   test(mergesort_r)偺寢壥:
//   丒Core i7-4500U	   63[ms]	VC++6.0,儕儕乕僗僺儖僪
//   丒P/ECE		12119[ms]	C尵岅斉qsort_r()
//   丒P/ECE		11377[ms]	傾僙儞僽儔斉qsort_r()
// - 仩峫嶡
//   丒堄奜偵傕qsort_r()傛傝傕mergesort_r()偺曽偑憗偄丅
//     忋婰偺寢壥偼mergesort_r()撪偺malloc/free偺帪娫傪娷傫偱偄傞偑丄偦傟偱傕mergesort_r()偺曽偑憗偄丅
//     偨偩偟丄崱夞偼僨乕僞偑戝偒偄偺偱malloc/free偑愯傔傞妱崌偑彫偝偄偩偗偱丄僨乕僞偑彫偝偄偲malloc/free偑愯傔傞妱崌偑戝偒偔側偭偰寢壥偑媡揮偡傞壜擻惈偼桳傞丅
//   丒摦揑側儊儌儕妋曐傪峴偭偰偄傞偲偄偆寚揰傪彍偗偽丄mergesort_r()偑埨掕僜乕僩偩偟寢峔椙偄傒偨偄偩丅
//     偙傟傑偱偼柍忦審偵qsort_r()傪巊偭偰偄偨偑丄崱屻偼mergesort_r()偺巊梡傕愊嬌揑偵専摙偟傛偆丅
//     摿偵丄摦揑儊儌儕妋曐偺僐僗僩偑彫偝偄PC娐嫬偱偼丄mergesort_r()傪愊嬌揑偵巊偭偰傕椙偝偦偆偩丅
//   丒尰忬偱偼heapsort_r()偑嬌抂偵抶偄丅
//     尰嵼偺heapsort_r()偼擔杮岅斉僂傿僉儁僨傿傾偺僸乕僾僜乕僩偺儁乕僕傪尒偰嶌偭偨偺偩偑丄偳偆傗傜僂傿僉儁僨傿傾偺僒儞僾儖偼偐側傝抶偄幚憰偱偁傞傛偆偩丅
//     嶲徠帒椏:乽DreamHope乿(http://www.dreamhope.net/)偝傫偺亀僸乕僾僜乕僩偱側偤嵞婣丠乣擔杮岅斉僂傿僉儁僨傿傾偺栤戣揰偲嵟嫮嵟懍偺僸乕僾僜乕僩乣亁(http://www.dreamhope.net/soliloquies/HeapSort/)
//     偄偢傟丄忋婰偺婰帠傪嶲峫偵偟偰丄heapsort_r()傪嶌傝捈偦偆丅	仼仼仼仼仼仼仼仼仼仼仼仼仼仼仼仼仼仼仼仼仼仼仼仼仼仼仼仼仼仼仼仼仼仼仼仼仼仼仼仼仼仼仼仼仼仼仼仼仼仼仼仼仼仼仼仼仼仼仼仼仼仼仼仼仼仼仼仼仼仼仼仼仼仼仼仼仼仼仼仼仸TODO:
