; Подреди във възходящ ред масив от RSI (RSI > 2) думи със знак, указан от 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

;/* Пирамида – двоично дърво, в което родителят е не по-малък от потомците си.
;void downHeap(int *a, int k, int n)	// Прегледай поддървото и премести
;{					// най-големия възел в корена му
;	int i, tmp;
;
;	n--;					// Премини към база 0
;	for (tmp = a[k]; k <= n / 2; k = i) {	// В корена запомни родителя
;		i = 2 * k;			// Ляв потомък
;		if (i < n && a[i] < a[i+1])	// Ако има десен, сравни го с
;			i++;			// левия и избери по-големия
;		if (tmp >= a[i])	// Ако родителят е по-голям или равен
;			break;		// на най-големия потомък, клонът е OK
;		a[k] = a[i];		// Иначе потомъкът застава на мястото
;	}				// на родителя
;	a[k] = tmp;	// Накрая родителят си разменя мястото с най-големия
;}			// потомък, освен ако е по-голям от всички потомци
;
;void heapSort(int *a, int n)		// Пирамидално сортиране (tri par tas)
;{					// Сортиращо дърво, heap, tas: пирамида
;	int i, tmp;
;
;	for (i = n / 2; i >= 0; i--)	// Създай сортиращо дърво (максималният
;		downHeap(a, i, n);	// елемент на масива ще бъде в корена)
;	for (i = n - 1; i > 0; i--) {
;		tmp = a[i];		// Размени местата на максимума
;		a[i] = a[0];		// и последния елемент на масива
;		a[0] = tmp;
;		downHeap(a, 0, i);	// Препострой сортиращото дърво за
;	}				// неотсортираната част от масива
;}
;*/

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;арг.:RDI,R9,RSI downHeap(a, i, n);
		DEC	RDX	; i--
	.until (sign?)	; ако i >= 0, продължи
	.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;арг.: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--;вече умалено
	.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