articles » current » assembly » x64 » procedures » qsort

x64 Assembly: Quick Sort (qsort) Procedure

The famous quicksort algorithm in x86-64 (64-bit) assembly

This code was compiled and tested on Visual Studio 2022.

This same procedure is available in x86 Assembly.

Quicksort is a great, reliable general purpose sorting algorithm. The TITLE is the C/C++ function declaration.

This short procedure can sort an array of pointers to strings or objects... or anything. compare_func must return less than zero when element1 is less than element2, zero when they are equal, and greater than zero when element1 is greater than element2.This version of quick sort uses insertion sort to sort smaller sub arrays.


TITLE 'extern "C" void qisort(void* array_to_sort[], const unsigned long long array_size, long long (*compare_func)(const void* element1, const void* element2));'

PUBLIC	qisort

_TEXT	SEGMENT

array_to_sort = 40
array_size = 48

qisort	PROC

	mov	QWORD PTR [rsp+16], rdx
	mov	QWORD PTR [rsp+8], rcx

	sub	rsp, 32

	cmp	QWORD PTR array_size[rsp], 30
	ja	quick_sort


insertion_sort:

	mov	r15, QWORD PTR array_to_sort[rsp]

	mov	r9, 1


insertion_sort_main_loop:

	mov	rax, QWORD PTR array_size[rsp]
	cmp	r9, rax
	jae	exit

	mov	r11, QWORD PTR [r15+r9*8]

	mov	r10, r9


insertion_sort_sub_loop:

	cmp	r10, 0
	jbe	SHORT exit_insertion_sort_sub_loop
	mov	rdx, QWORD PTR [r15+r10*8-8]
	mov	rcx, r11
	call	r8 ; call the compare_func function
	test	rax, rax
	jge	SHORT exit_insertion_sort_sub_loop

	mov	rdx, QWORD PTR [r15+r10*8-8]
	mov	QWORD PTR [r15+r10*8], rdx


	dec	r10 ; r10 is a local variable used for indexing

	jmp	SHORT insertion_sort_sub_loop


exit_insertion_sort_sub_loop:

	mov	QWORD PTR [r15+r10*8], r11

	inc	r9 ; r9 is a local variable used for indexing

	jmp	insertion_sort_main_loop


quick_sort:

	mov	rax, QWORD PTR array_size[rsp]
	shr	rax, 1 ; divide array_size by 2
	mov	r15, QWORD PTR array_to_sort[rsp]
	mov	r12, QWORD PTR [r15+rax*8]

	mov	r14, r15 ; move array_to_sort to left (r14)

	mov	rax, r15 ; load array_to_sort pointer value
	mov	r15, QWORD PTR array_size[rsp] ; load array_size
	lea	r13, QWORD PTR [rax+r15*8-8] ; the right (r13) equals array_to_sort + array_size - 8 bytes


quick_sort_sub_loop_1:

	cmp	r14, r13 ; compare left (r14) to right (r13)
	ja	SHORT quick_sort_sub_loop_2
	mov	rdx, r12 ; move pivot into rdx for call compare_func
	mov	rcx, QWORD PTR [r14] ; move left into rcx for call compare_func
	call	r8 ; call the compare_func function
	test	rax, rax
	jge	SHORT quick_sort_sub_loop_2
	add	r14, 8 ; increment left (r14) eight bytes
	jmp	SHORT quick_sort_sub_loop_1


quick_sort_sub_loop_2:

	cmp	r14, r13 ; compare left (r14) to right (r13)
	ja	SHORT quick_sort_check_left_greater_than_right
	mov	rdx, r12 ; move pivot into rdx for call compare_func
	mov	rcx, QWORD PTR [r13]
	call	r8 ; call the compare_func function
	test	rax, rax
	jle	SHORT quick_sort_check_left_greater_than_right
	sub	r13, 8 ; decrement right (r13) eight bytes
	jmp	SHORT quick_sort_sub_loop_2


quick_sort_check_left_greater_than_right:

	cmp	r14, r13 ; compare left (r14) to right (r13)
	jbe	SHORT quick_sort_swap

	jmp	SHORT call_quick_sort


quick_sort_swap:

	mov	r11, QWORD PTR [r14] ; move left (r14) value to temp varaible (r11)

	mov	rcx, QWORD PTR [r13] ; move right (r13) value to rcx
	mov	QWORD PTR [r14], rcx ; move ecx to left (r14) value
	add	r14, 8 ; increment left (r14) eight bytes

	mov	QWORD PTR [r13], r11
	sub	r13, 8 ; decrement right (r13) eight bytes

	jmp	quick_sort_sub_loop_1


call_quick_sort:

	mov	rax, QWORD PTR array_to_sort[rsp]
	mov	rcx, r13 ; move right (r13) to rcx
	sub	rcx, rax
	mov	rdx, rcx
	sar	rdx, 3
	inc	rdx ; rdx is the new array_size value (right - array_to_sort + 8 bytes)
	mov	rcx, QWORD PTR array_to_sort[rsp] ; rcx is the pointer to array_to_sort
	call	qisort ; r8 is already set to compare_func

	mov	rax, QWORD PTR array_to_sort[rsp]
	mov	rcx, QWORD PTR array_size[rsp]
	lea	rax, QWORD PTR [rax+rcx*8]
	sub	rax, r14 ; subtract left (r14 - pointer) from rax
	sar	rax, 3
	mov	rdx, rax ; set rdx to new array_size (array_to_sort - array_size * 8 - left (r14))
	mov	rcx, r14 ; set rcx to left (r14) which is the new array_to_sort value
	call	qisort ; r8 is already set to compare_func


exit:

	add	rsp, 32
	ret	0
qisort	ENDP
_TEXT	ENDS
END

This site uses cookies. Cookies are simple text files stored on the user's computer. They are used for adding features and security to this site. Read the privacy policy.
CLOSE