;歸并排序算法。
DATS	EQU	20H	;待排序數(shù)據(jù)（原列）所在頁面。
N	EQU	5DH	;單字節(jié)數(shù)據(jù)個數(shù)（不超過255個）。
DATS1	EQU	21H	;緩沖區(qū)（新列）所在頁面。

	ORG	0000H
	LJMP	TEST
	
	ORG	100H
TEST:	MOV	DPTR,#LIST;將測試數(shù)據(jù)拷貝到片外RAM中。
	MOV	P2,#DATS
	MOV	R0,#0
	MOV	R2,#N
COPY:	CLR	A
	MOVC	A,@A+DPTR
	MOVX	@R0,A
	INC	DPTR
	INC	R0
	DJNZ	R2,COPY
	LCALL	MGSORT	;測試歸并排序算法。
STOP:	LJMP	STOP	;測試結束。

MGSORT:	MOV	R3,#1	;初始化子列長度為1個數(shù)據(jù)元素。
LOOP:	MOV	P2,#DATS;從原列，
	MOV	DPH,#DATS1;到新列，
	LCALL	MGPASS	;調用一輪歸并算法。
	MOV	P2,#DATS1;從新列，
	MOV	DPH,#DATS;到原列，
	LCALL	MGPASS	;再調用一輪歸并算法，使結果保存在原列中。
	JC	LOOPE	;長度超過255個元素，排序結束。
	MOV	A,R3	;取下一輪子列長度。
	CLR	C
	SUBB	A,#N	;和待排序數(shù)據(jù)總數(shù)相比。
	JC	LOOP	;未覆蓋全部數(shù)據(jù)元素，繼續(xù)歸并。
LOOPE:	RET		;已覆蓋全部數(shù)據(jù)元素，歸并結束。

MGPASS:	MOV	R7,#N	;一輪歸并算法，初始化全部元素均未處理。
	MOV	R0,#0
	MOV	DPL,#0
MERGS:	MOV	A,R7	;取尚未處理元素個數(shù)。
	JZ	MERGSE	;沒有未處理元素，該輪歸并結束。
	CLR	C
	SUBB	A,R3	;從中截取一個子列，作為左子列。
	JNC	MERGS2	;可以截取到一個完整的左子列。
MERGS1:	MOV	A,R0	;左子列不夠一個完整子列的長度時，
	MOV	R1,A	;直接轉抄到目標列。
	MOV	A,R7	;將全部剩余元素，作為轉抄對象。
	MOV	R2,A
	LCALL	MOVS	;進行轉抄。
MERGSE:	MOV	A,R3	;將該輪歸并算法的子列長度加倍。
	CLR	C
	RLC	A
	MOV	R3,A	;作為下一輪歸并算法的子列長度。
	RET		;結束本輪歸并算法。
MERGS2:	JZ	MERGS1	;剛好夠一個完整的左子列，進行轉抄。
	MOV	R7,A	;保存截取一個完整的左子列后的剩余元素個數(shù)。
	MOV	A,R3
	MOV	R6,A	;左子列長度為指定長度。
	MOV	A,R0	;取左子列起始地址，
	ADD	A,R3	;加上左子列長度，
	MOV	R1,A	;得到右子列起始地址。
	MOV	A,R7	;取截取一個完整的左子列后的剩余元素個數(shù)。
	CLR	C
	SUBB	A,R3	;從中再截取一個子列，作為右子列。
	JNC	MERGS3	;能夠截取到一個完整的右子列。
	MOV	A,R7	;否則，將全部剩余元素，作為右子列的長度。
	MOV	R5,A
	MOV	R7,#0	;再沒有剩余元素了。
	SJMP	MERGS4	;準備進行歸并操作。
MERGS3:	MOV	R7,A	;保存截取右子列后的剩余元素個數(shù)。
	MOV	A,R3
	MOV	R5,A	;一個完整的右子列。
MERGS4:	MOV	A,R0	;將當前的左子列起始地址，
	ADD	A,R6	;加上左子列長度，
	ADD	A,R5	;再加上右子列長度，
	MOV	R4,A	;得到下一次歸并操作的左子列首址，保存之。
	LCALL	MERGE	;調用將兩個有序子列進行歸并的算法。
	MOV	A,R4	;調整左子列首址，
	MOV	R0,A
	LJMP	MERGS	;繼續(xù)進行下一次歸并操作。

MERGE:	MOVX	A,@R1	;讀取右子列未處理的元素。
	MOV	B,A	;暫存。
	MOVX	A,@R0	;讀取左子列未處理的元素。
	CLR	C
	SUBB	A,B	;比較兩者大小。
	JC	MERG1	;左小轉移。
	MOVX	A,@R1	;右小或相等，取右子列元素，
	MOVX	@DPTR,A	;轉抄到目標列。
	INC	R1	;調整右子列指針。
	INC	DPTR	;調整目標指針，指向下一個存放地址。
	DJNZ	R5,MERGE;右子列元素若未全部處理完畢，則繼續(xù)歸并。
	MOV	A,R0	;右子列全部處理完畢，準備轉抄左子列剩余元素。
	MOV	R1,A
	MOV	A,R6	;取左子列剩余元素個數(shù)，
	MOV	R2,A	;控制轉抄元素個數(shù)。
	SJMP	MOVS	;進行轉抄，結束這次歸并操作。
MERG1:	MOVX	A,@R0	;左小，取左子列元素，
	MOVX	@DPTR,A	;轉抄到目標列。
	INC	R0	;調整左子列指針。
	INC	DPTR	;調整目標指針，指向下一個存放地址。
	DJNZ	R6,MERGE;左子列元素若未全部處理完畢，則繼續(xù)歸并。
	MOV	A,R5	;左子列全部處理完畢，準備轉抄右子列剩余元素。
	MOV	R2,A	;控制轉抄元素個數(shù)。
MOVS:	MOVX	A,@R1	;進行轉抄。
	MOVX	@DPTR,A
	INC	DPTR
	INC	R1
	DJNZ	R2,MOVS
	RET		;將指定數(shù)目的元素轉抄完畢。

LIST:	DB	70H,90H,1EH,87H	;93個單字節(jié)測試數(shù)據(jù)。
	DB	9FH,0F3H,93H,6BH
	DB	8EH,14H,04H,7FH
	DB	75H,43H,7DH,1AH
	DB	7CH,0FH,0A4H,0CCH
	DB	0BCH,55H,3BH,4EH
	DB	02H,0A5H,3FH,0BFH
	DB	2AH,0B9H,80H,34H
	DB	8CH,0C3H,0D1H,41H
	DB	0A8H,40H,17H,01H
	DB	1BH,4FH,3DH,72H
	DB	0B6H,9DH,4CH,3CH
	DB	0B3H,03H,1CH,66H
	DB	38H,5CH,0C6H,45H
	DB	0E1H,0B0H,0ABH,30H
	DB	5BH,07H,27H,12H
	DB	0D6H,0E7H,60H,63H
	DB	0EH,0C8H,88H,99H
	DB	95H,0A2H,0C0H,5AH
	DB	0D3H,23H,0CAH,0DBH
	DB	79H,58H,5FH,0F5H
	DB	4AH,32H,0DEH,0F2H
	DB	0E3H,0D8H,59H,2FH,31H
	END