; Sort in ascending order an array of RSI ( > 2) signed words pointed to by RDI
; Ingo Wegener: Bottom-up Heapsort, a new variant of Heapsort beating, on an
; average, Quicksort (if n is not very small), Theoretical Comp. Science '93

;/* Heap - a binary tree in which the parent is not lesser than its children.
;void downHeap(int *a, int k, int n)	// Examine the sub-tree and move the
;{					// greatest node to its root
;	int i, tmp;
;
;	n--;					// Switch to base 0
;	for (tmp = a[k]; k <= n / 2; k = i) {	// Save the parent in the root
;		i = 2 * k;			// Left child
;		if (i < n && a[i] < a[i+1])	// Right child? Compare it to
;			i++;		// the left one & choose the larger one
;		if (tmp >= a[i])	// If the parent's larger than or equal
;			break;		// to the largest child the branch's OK
;		a[k] = a[i];		// Else the child takes its parent's
;	}				// place
;	a[k] = tmp;	// Finally the parent swaps its place with the largest
;}			// child unless it's bigger than all the children
;
;void heapSort(int *a, int n)		// Heap (pyramidal) sort (tri par tas)
;{					// Sorting tree, heap, tas: a pyramid
;	int i, tmp;
;
;	for (i = n / 2; i >= 0; i--)	// Create a sorting tree (largest mem-
;		downHeap(a, i, n);	// ber of the array will be at its root
;	for (i = n - 1; i > 0; i--) {
;		tmp = a[i];		// Swap the maximal and the last
;		a[i] = a[0];		// members of the array
;		a[0] = tmp;
;		downHeap(a, 0, i);	// Rebuild the sorting tree for the
;	}				// non-sorted part of the array
;}
;*/

option prologue:none, epilogue:none
.code
heapSort proc
_heapSort proc		;	  void heapSort(int *a, int n)
	MOV	RDX,RSI	; i = n	  {	  int i, tmp;	// RDX (RSI), RCX
	SHR	RDX,1	; i = n / 2	  for (i = n / 2; i >= 0; i--)
	DEC	RSI	; n--
	.repeat
		MOV	R9,RDX	; i
		CALL	DOWNHEAP;arg.:RDI,R9,RSI downHeap(a, i, n);
		DEC	RDX	; i--
	.until (sign?)	; if i >= 0, continue
	.repeat
		XOR	R9,R9	; k = 0	  for (i = n - 1; i > 0; i--) {
		MOV	RCX,[RDI+8*RSI];	  tmp = a[i];
		XCHG	RCX,[RDI];_________ _____ a[i] = a[0];
		MOV	[RDI+8*RSI],RCX;___X_____ a[0] = tmp;
		DEC	RSI	; i-- (n--)
		CALL	DOWNHEAP;arg.:RDI,RDX,RSI downHeap(a, 0, i);
	.until (RSI == 0)	;	  }
	RET			; }
_heapSort endp
heapSort endp
DOWNHEAP proc		;	  void downHeap(int*a,int k,int n)// RDI,R9,RSI
	MOV	RCX,[RDI+8*R9]	; {	  int i,tmp;/*R10,RCX*/n--;already decr
	.for ( : : )		;	  for (tmp = a[k]; k <= n / 2; k = i) {
		MOV	R8,RSI	; n
		SHR	R8,1	; n / 2
		.break .if (R9 > R8); k <= n / 2 ?
		LEA	R10,[2*R9];		  i = 2 * k;
		.if (R10 < RSI)	;		  if (i < n &&
			MOV	R8,[RDI+8*R10];		       a[i] < a[i+1])
			CMP	R8,[RDI+8*R10+8]
			.if (less?)
				INC	R10;		  i++;
			.endif
		.endif
		MOV	R8,[RDI+8*R10]
		CMP	RCX,R8	;		  if (tmp >= a[i])
		.break .if (!less?);		      break;
		MOV	[RDI+8*R9],R8;		  a[k] = a[i];
		MOV	R9,R10	; k = i
	.endfor			;	  }
	MOV	[RDI+8*R9],RCX	;	  a[k] = tmp;
	RET			; }
DOWNHEAP endp
end