title	IN MEMORY SHELL-metzner sort
	subttl	from KILOBAUD april 1981 p164
;
.comment *
	'For fixed length records stored in memory
	put no. of records in n1 and m1. the length
	of each record is stored at k1, and the starting
	address at j1. start sort by calling location
	"ENTRY". to change to descending sort change the
	instruction at neq: to dah.'
	 *
;
n1:	dw	0		; number of records
m1:	dw	0		; ..same here
k1:	dw	0		; length of records
j1:	dw	0		; starting address of strings
i1:	dw	0		; ptr
ml1:	dw	0		; ptr
dj1:	dw	0		; ptr
di1:	dw	0		; Ptr
;
	.z80

entry:	ld	hl,(j1)		; get start address
	push	hl		; ..save
	ld	hl,(k1)		; get length
	push	hl		; ..it too
div:	xor	a		; m1=m1/2
	ld	hl,(m1)
	ld	a,h
	rra
	ld	h,a
	ld	a,l
	rra
	ld	l,a
	ld	(m1),hl		; save new m1
;
	or	h		; check if done
	jp	nz,ndon
	pop	bc		; finished
	pop	de		; ..so return
	ret			; ...now
;
;	set k1=n1-m1
;
ndon:	ex	de,hl		; m1 to de
	ld	hl,(n1)
	ld	a,l
	sub	e
	ld	l,a
	ld	a,h
	sbc	a,d
	ld	h,a
	ld	(k1),hl
	ld	hl,1		; set and save i=j=1
	ld	(j1),hl
	ld	(i1),hl
;
;	calc & save addr offset = m1*i1
;
	dec	l
	pop	bc		; length of str=i1
	push	bc		; ..put it back
lp1:	add	hl,de
	dec	bc
	ld	a,b
	or	c
	jp	nz,lp1
	ld	(ml1),hl
;
	ex	de,hl		; calc & save d(j), d(i), d(i+m)
	pop	bc
	pop	hl
	push	hl
	push	bc
lp2:	ld	(dj1),hl
	ld	(di1),hl
	ex	de,hl
	add	hl,de
	ex	de,hl		; HL has d(i), DE has d(i+m)
;
;	compare strings and switch
;
cp1:	pop	bc		; len of string=l1
	push	bc
lp3:	ld	a,(de)		; compare each byte
	sub	(hl)
	jp	nz,neq		; not equal
	inc	hl		; if =, then next byte
	inc	de
	dec	bc
	ld	a,b
	or	c
	jp	nz,lp3
	jp	nsw		; if done, don't switch
;
;	change next instruction to jc for descending
;
neq:	jp	nc,nsw		; if d(i)<d(i+m) don't switch
;
sw:	push	bc		; switch bytes not equal
	ld	b,(hl)
	ld	a,(de)
	ld	(hl),a
	ld	a,b
	ld	(de),a
	inc	hl
	inc	de
	pop	bc
	dec	bc
	ld	a,b
	or	c
	jp	nz,sw
;
;	strings switched, chk if i1-m1 < 1
;
	ld	hl,(m1)
	ld	a,h
	cpl
	ld	d,a
	ld	a,l
	cpl
	ld	e,a
	ld	hl,(i1)
	add	hl,de		; if i1-m1<1 then jump to same as
				; ..no switch
	jp	nc,nsw
;
;	calc new d(i), d(i+m)
;
	inc	hl		; save	new i1=i1-m
	ld	(i1),hl
	ld	hl,(di1)	; old d(i)=new d(i+m)
	ex	de,hl
	ld	hl,(ml1)	; address offset
	ld	a,e		; new d(i)=old d(i)-offset
	sub	l
	ld	l,a
	ld	a,d
	sbc	a,h
	ld	h,a
	ld	(di1),hl	; save new d(i)
	jp	cp1		; goto compare strings
;
;	check for j>k
;
nsw:	ld	hl,(j1)
	inc	hl		; save new j=old j+1
	ld	(j1),hl
	ld	(i1),hl
	ex	de,hl
	ld	hl,(k1)
	ld	a,l
	sub	e
	ld	a,h
	sbc	a,d
	jp	c,div		; if j>k goto beginning and
				; ..divide m1
;
;	calc new d(j), d(i)
;
	ld	hl,(dj1)
	pop	de
	push	de
	add	hl,de		; new d(j)=old d(j+1)
	ex	de,hl
	ld	hl,(ml1)
	ex	de,hl
	jp	lp2
;
; that all folks
;
	end	entry