# PROWAREtech

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.

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(n2). 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.

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

• Worst-case performance is O(n2), 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:

ret	0
qisort	ENDP
_TEXT	ENDS
END
``````