;;  quicksort in assembly by Chuck Liang.
	;;  quicksort wraps around quickaux
	
.386p
.model flat, C
.stack
.data
.code
	;; [ebp+8] is start address, [ebp+12] is end address of partition
quickaux proc
	push ebp
	mov ebp,esp
	pushad

	mov ebx,[ebp+8]		; start of partition
	;;  find pivot index:	
ploop:
	cmp ebx,[ebp+12]	;  last cell of partition?
	jge qretrn		;  no pivot, so exit
	mov eax, [ebx+4]	;  A[i+1]
	cmp eax, [ebx]		;  A[i]
	jl pfound		;  A[i]>A[i+1], pivot found
	add ebx,4		;  next cell
	jmp ploop
pfound:
	;;  at this point, ebx holds mem address of pivot
	;;  now partition into < and >= pivot via repeated swapping.
	;;  use two counters:	 ebx and esi.  ebx always points to the
	;;  first cell of second partition (what's >= pivot)
	mov ecx,[ebx]		;  save pivot in ecx
	mov esi,ebx
	add esi,4		;  next cell
tloop:				;  partitioning loop
	cmp ecx,[esi]		;  compare pivot against element
	jle noswap		;  no swap if element >=pivot
	;;  swap [ebx] and [esi], advance both
	mov eax,[ebx]
	push eax		;  use stack as temp
	mov eax,[esi]
	mov [ebx],eax
	pop eax
	mov [esi],eax		;  done swap
	add ebx,4		;  next cell must still be >= pivot
noswap:				
	add esi,4		;  goto next cell, preserve ebx
	cmp esi,[ebp+12]	;  end of partition?
	jle tloop		;  next iteration of partition loop

	;;  at this point, ebx holds start addr of second partition
	;;  (could be pivot itself).
	;;  make recursive calls to quickaux:	

	;;  first partition:
	sub ebx,4
	push ebx		;  end of first paritition
	mov eax,[ebp+8]		 
	push eax		;  start of first partition
	call quickaux
	add esp,8		;  deallocate params
	;;  second partition
	mov eax,[ebp+12]
	push eax		;  end of second partition
	add ebx,4
	push ebx		;  start of second partition
	call quickaux
	add esp,8
	
qretrn:
	popad
	mov esp,ebp
	pop ebp
	ret
quickaux endp


	;;  the quicksort procedure is just a wrapper around quickaux,
	;;  for ease of integration into high level language.
	;; void quicksort(int *A, int start, int end)
quicksort proc
	push ebp
	mov ebp,esp
	pushad
	mov ebx,[ebp+8]		;  start addr of array
	mov eax,[ebp+16]	;  end index of partition
	shl eax,2		;  multiply by 4: sizeof(int)==4
	add eax,ebx		;  eax holds end addr of partition
	mov ecx,[ebp+12]	;  start index of partition
	shl ecx,2
	add ecx,ebx		;  start addr of partition
	push eax		;  quickaux expects start and end 
	push ecx		;    addresses of partition as arguments.
	call quickaux		
	add esp,8
	popad
	mov esp,ebp
	pop ebp
	ret
quicksort endp
end


	;; FYI: quicksort in Prolog: 

; pivot([A,B|T],A) :- A > B, !.
; pivot([A,B|T],C) :- pivot([B|T],C).
;
; partition(Pv,[A|T],[A|As],B) :- A < Pv, partition(Pv,T,As,B).
; partition(Pv,[A|T],B,[A|As]) :- A >= Pv, partition(Pv,T,B,As).
; partition(Pv,[],[],[]).
; 
; quicksort(A,B) :- 
;   pivot(A,P), !, 
;   partition(P,A,L,M),
;   quicksort(L,SL), quicksort(M,SM),
;   append(SL,SM,B).
; quicksort(A,A).