* 符号あり(int)/なし(unint)データ配列 ソート（降順:大→小／昇順:小→大 共通ソース）
* （クイックソート：Ｏｈ！Ｘ　１９９１／３　ｐ７４より）
*

*	BLT1		blt	* 符号有り降順
*	BLT1		bgt	* 符号有り昇順
*	BLT1		bcs	* 符号無し降順
*	BLT1		bhi	* 符号無し昇順

*	BLT2		bgt	* 符号有り降順
*	BLT2		blt	* 符号有り昇順
*	BLT2		bhi	* 符号無し降順
*	BLT2		bcs	* 符号無し昇順

*	BLT3		bge	* 符号有り降順
*	BLT3		ble	* 符号有り昇順
*	BLT3		bcc	* 符号無し降順
*	BLT3		bls	* 符号無し昇順


SZ	equ	4			* 要素のサイズ=sizeof(unintまたは/unt)
M	equ	15			* 区間内の要素数がM未満になったら単純挿入法に
					* 切り替える

	.offset	8
ATOP:	.ds.l	1			* 配列の先頭アドレス
	.ds.l	1			* 配列の要素数

	.text
	.even

_quisort:
	link	a6,#0
	movem.l	d3/a3-a4,-(sp)
	movem.l	ATOP(a6),a0/a3		* a0=配列先頭アドレス , a3=配列要素数
	add.l	a3,a3
	add.l	a3,a3			* *4=byte size
	lea	(a0,a3.l),a3		* a3=配列最終アドレス＋SZ
	moveq.l	#$ffff_fffc,d2		* 下位２ビットマスクデータ
	moveq.l	#M*SZ,d3		* 切り替え点
	clr.l	-(sp)			* スタック底の印
	bra.s	loop0

retry:	move.l	d0,a0			* a0=区間先頭
	move.l	(sp)+,a3		* a3=区間末尾＋１
loop0:	move.l	a3,d0
	sub.l	a0,d0			* d0=区間バイト数
	cmp.l	d3,d0
	bcs	isort			* 区間が十分小さくなったら単純挿入法に変更
	
	lsr.l	#1,d0			* d0=区間バイト数／２
	and.l	d2,d0			* d0=中央のインデックス
	
	lea.l	(a0,d0.l),a4		* a4=区間中央
	move.l	(a4),d0			* d0=境界値
	move.l	a0,a1			* a1=左端
	move.l	a3,a2			* a2=右端
	bra.s	loop2

loop1:	* 分割する
	move.l	-(a1),d1		* ２要素を交換する
	move.l	(a2),(a1)+
	move.l	d1,(a2)
loop2:	cmp.l	(a1)+,d0		* 左側から位置のおかしい要素を探す
	BLT1	loop2
loop3:	cmp.l	-(a2),d0		* 右側から位置のおかしい要素を探す
	BLT2	loop3
	cmp.l	a1,a2			* ポインタがすれちがうまで
	bcc	loop1			* 繰りかえす
	
	subq.w	#SZ,a1			* 行きすぎた分の補正
	* 分割終了
	cmp.l	a4,a1
	bcc	right
left:	movem.l	a1/a3,-(sp)		* 右区間をスタックに積み
	move.l	a1,a3			* 左の分割を先に行う
	bra	loop0
right:	movem.l	a0/a1,-(sp)		* 左区間をスタックに積み
	move.l	a1,a0			* 右区間の分割を先に行う
	bra	loop0
*
isort:	* 単純挿入法
	lea.l	-SZ(a3),a2
	bra.s	inext
iloop:	move.l	(a1)+,d1
	cmp.l	d1,d0
	BLT3	found
	move.l	d1,-SZ*2(a1)
	cmp.l	a3,a1
	bcs	iloop
	addq.w	#SZ,a1
found:	move.l	d0,-SZ*2(a1)
inext:	move.l	a2,a1
	move.l	-(a2),d0
	cmp.l	a0,a2
	bcc	iloop
*
next0:	move.l	(sp)+,d0		* スタック上に別区間がなければ終了
	bne	retry			* スタックの底が見えたら終了
done:	movem.l	(sp)+,d3/a3-a4
	unlk	a6
	rts

	.end
