; Himpelsoft C++ Project:
	; Library-Modul "quicksort"
	; Jens Gelhar 11.02.94

	xdef _qsort,qsort__PvUiUiPFiPCvPCvp

	xref uintmult

_qsort:
qsort__PvUiUiPFiPCvPCvp:
	; Stack-Parameter: 0 Zeiger auf Vector
	;                  4 Elementanzahl
	;                  8 Elementgroesse
	;                 12 Vergleichsfunktion
	movem.l	d2/d3/a2/a6,-(a7)
	move.l 	20+0(a7),a0	; Zeiger auf Vector
	move.l	20+4(a7),d3	; Elementanzahl
	move.l	20+8(a7),d2	; Elementgröße
	move.l	20+12(a7),a6	; Vergleichsfunktion
	cmp.l	#1,d2
	beq.b	.1
	blo.b	.pop
	addq.l	#1,d2
	and.w	#$FFFE,d2	; Word-Alignment
.1	move.l	d3,d1
	move.l	d2,d0
	jsr	uintmult
	add.l	a0,d0
	sub.l	d2,d0
	move.l	d0,a1		; Vectorende (letztes Element) nach a1
	bsr.b	qsrek
.pop	movem.l	(a7)+,d2/d3/a2/a6
	rts

qsrek:	; Rekursion: von a0 bis einschl. a1 d3 Elemente der Groesse d2, Vergleichen mit a6
	cmp.l	a1,a0
	bhs.b	.ret		; Vector leer bzw. nur ein Element

	move.l	d3,d1
	lsr.l	#1,d1
	move.l	d2,d0
	jsr	uintmult
	add.l	a0,d0
	move.l	d0,a2		; Vectormitte
	bsr.b	qswap		; Vergleichselement an erste Stelle
	move.l	a0,a2		; "last" nach a2
	move.l	d3,-(a7)	; Anzahl merken
	move.l	a0,-(a7)	; Anfang merken
	add.l	d2,a0		; erstes Element überspringen
	moveq	#0,d3		; d3: Index von "last"
.loop	cmp.l	a1,a0
	bhi.b	.end
	; Vergleichen:
	movem.l	a0/a1,-(a7)
	move.l	8(a7),-(a7)
	move.l	a0,-(a7)
	jsr	(a6)
	addq.l	#8,a7
	movem.l	(a7)+,a0/a1
	tst.l	d0
	bpl.b	.next
	add.l	d2,a2		; "last"-Zeiger weitersetzen
	addq.l	#1,d3
	bsr.b	qswap		; vertauschen
.next	add.l	d2,a0
	bra.b	.loop
.end	; Schleifenende
	move.l (a7)+,a0         ; Anfangszeiger
	bsr.b qswap             ; Vergleichselement zurücktauschen
	; erste Rekursion:
	movem.l	d3/a1/a2,-(a7)
	move.l	a2,a1		; neuer Endzeiger:
	sub.l	d2,a1
	bsr.b	qsrek		; übrige Parameter stimmen schon
	; zweite Rekursion:
	movem.l	(a7)+,d0/a1/a2
	move.l	a2,a0
	add.l	d2,a0		; Mitte+1 = neuer Anfang
	move.l	(a7)+,d3	; Gesamtanzahl
	sub.l	d0,d3
	subq.l	#1,d3		; Anzahl
	bra.b	qsrek		; und wieder absteigen
.ret	rts

qswap:	; Elemente a0 und a2 vertauschen, Seiteneffekt auf d0 und d1
	cmp.l	a0,a2
	beq.b	.0
	move.l	d2,d0
	add.l	d2,a0
	add.l	d2,a2
.loop	move.b	-(a0),d1
	move.b	-(a2),(a0)
	move.b	d1,(a2)
	subq.l	#1,d0
	bhi.b	.loop
.0	rts

	end