****************************************************************************
* THIS IS NOT A STANDALONE SOURCE!
* You can compile and assemble it, but you can't run it!!!
*
* The procedures below execute the sorting on a vector of 32-bit signed
* integers using the MergeSort algorythm.
*
* Note that these are meant to be examples only, so optimization has been
* sacrificed to enhance the readability (BTW: ESA isn't indicated at all
* for this kinda things...).
*
* To use them you need an integers vector of any length and an auxiliary
* vector of the same length (size in bytes = number of integers * 4).
****************************************************************************

****************************************************************************
* MergeSort 1.0.1
****************************************************************************
* INFO	sorts in ascending order a vector of signed long integers
* SYN	MergeSort[SouVecAdr,AuxVecAdr,FII,LII]
*	          a0        a1        d0  d1
* IN	SouVecAdr	pointer to vector to sort
*	AuxVecAdr	address of auxiliary vector
*	FII	First Item Index (tipically 0)
*	LII	Last Item Index (tipically # of integers-1)
* NOTE	vector items are .l
****************************************************************************

	procedure MergeSort[a0-a1/d0-d1],d2-d3
	when.s d0«d1

	 move.l	d0,d3
	 add.l	d1,d3
	 lsr.l	#1,d3	;(FEI+LEI)/2
	 MergeSort[sav:a0,a1,d0,d3]

	 addq.l	#1,d3	;(FEI+LEI)/2+1
	 MergeSort[sav:a0,a1,d3,d1]

	 move.l	d1,d2
	 merge[sav:a0,a1,d0,d3,d2]

	ewhen
	eproc

****************************************************************************
* merge 1.0.1
****************************************************************************
* INFO	core of MergeSort algorhytm
* SYN	merge[SouVecAdr,AuxVecAdr,FHI,SHI,LII]
*	      a0        a1        d0  d1  d2
* IN	SouVecAdr	pointer to vector to sort
*	AuxVecAdr	pointer to auxiliary vector
*	FHI	First Half Index
*	SHI	Second Half Index
*	LII	Last Item Index
****************************************************************************

	procedure	merge[a0-a1/d0-d2],a0/d3-d7
	move.l	d0,d3	;i=FHI
	move.l	d0,d4	;FHI
	move.l	d1,d5	;SHI

	while.s d3«=d2	;while i<=LEI

	 when.s d4=d1	;if FH items over
                  move.l	(a0,d5.l*4),(a1,d3.l*4)	;AuxVecAdr[i]=SouVecAdr[SHI]
	  addq.l	#1,d5	;increment SHI
	 owhen  d5»d2	;if SH items over
	  move.l	(a0,d4.l*4),(a1,d3.l*4)	;AuxVecAdr[i]=SouVecAdr[FHI]
	  addq.l	#1,d4	;increment FHI
	 othw
	  move.l	(a0,d4.l*4),d6	;SouVecAdr[FHI]
	  move.l	(a0,d5.l*4),d7	;SouVecAdr[SHI]

	  when.s d6<=d7	;if SouVecAdr[FHI]<=SouVecAdr[SHI]
	   move.l	d6,(a1,d3.l*4)	;AuxVecAdr[i]=SouVecAdr[FHI]
	   addq.l	#1,d4	;increment FHI
	  othw		;if SouVecAdr[FHI]<SouVecAdr[SHI]
	   move.l	d7,(a1,d3.l*4)	;AuxVecAdr[i]=SouVecAdr[SHI]
	   addq.l	#1,d5	;increment SHI
	  ewhen

	 ewhen

	 addq.l	#1,d3	;increment i
	ewhile

	for d3 = d0 upto d2
	 move.l	(a1,d3.l*4),(a0,d3.l*4)
	next.s

	eproc