x64 Assembly: Quick Sort (qsort) Procedure

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.

Quicksort is a highly efficient and widely used sorting algorithm that employs the divide-and-conquer strategy. Here are the key aspects of the quicksort algorithm:

Basic Idea

Quicksort works by selecting a 'pivot' element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. The sub-arrays are then sorted recursively.

Steps of Quicksort

1. Choose a Pivot: Select an element from the array to serve as the pivot. Various strategies exist for choosing the pivot, such as picking the first element, the last element, a random element, or the median.

2. Partitioning: Rearrange the array so that elements less than the pivot are on the left, elements greater than the pivot are on the right, and the pivot is in its final position. This process is called partitioning.

3. Recursively Sort Sub-arrays: Apply the same process recursively to the sub-arrays of elements with smaller and larger values.

Key Points

• Time Complexity: The average-case time complexity is O(n•log(n)) O(n•log(n)), where n is the number of elements to be sorted. In the worst case, which occurs when the smallest or largest element is always chosen as the pivot, the time complexity is O(n²). However, with good pivot selection (e.g., using the median-of-three rule), the average case is more likely.
• Space Complexity: Quicksort is an in-place sorting algorithm, meaning it requires only a small, constant amount of extra storage space (i.e., O(log(n)) due to the recursion stack).
• Stability: Quicksort is not a stable sort, meaning that the relative order of equal sort items is not preserved.

Advantages and Disadvantages

Advantages:

• Generally faster than other (n•log(n)) algorithms like merge sort and heap sort for most inputs.
• In-place sorting, requiring minimal additional memory.

Disadvantages:

• Worst-case performance is O(n²), though this can be mitigated with good pivot selection.
• Not stable, so it may not be suitable when the stability of equal elements is required.

Practical Considerations

• Pivot Selection: Strategies like random pivot, median-of-three (selecting the median of the first, middle, and last elements), and others help avoid the worst-case scenarios.

Quicksort is widely used due to its efficiency and simplicity, especially for large datasets. Its performance can be significantly improved with good pivot selection and implementation optimizations.

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

---