QuickSort algorithm

[jj2007]

 

Code: [Select]

mov rsi,offset array1 ; In this example, we'll use
mov rdi,offset indx   ; RSI and RDI to point to bases of arrays

;call the QuickSort procedure
mov rcx,30 ; array of 30 elements
mov rdx,offset indx
mov r8,loadValueToCmp ; load pointer to procedure
mov r9, offset isItLess ; load pointer to procedure
mov r10, offset isItMore ; load pointer to procedure
SortAny proto
call SortAny ; somewhere in here appears my stack misaligned at... message; the procs!
;result in 'indx' or at [RDI]...

Code: [Select]

  xor rbx, rbx
  .Repeat
mov rax, offset indx
lea rax, [rax+4*rbx]
mov eax, [rax]
Print Str$(" \nRes=%i", eax)
inc rbx
  .Until rbx>=30

Code: [Select]

Res=29
Res=28
Res=27
Res=26
Res=25
Res=24
Res=23
Res=22
Res=21
Res=20
Res=19
Res=18
Res=17
Res=16
Res=15
Res=14
Res=13
Res=12
Res=11
Res=10
Res=9
Res=8
Res=7
Res=6
Res=5
Res=4
Res=3
Res=2
Res=1
Res=0

[i Z !]

That's great, thanks. I might use your code for printing out in my next examples.

To anyone interested, I've added an example for sorting REAL8 values in my "example post" (the 3rd post in this topic)

[i Z !]

Corrections and performance improvements in v4. Examples also added to my first post.

[jj2007]

Found on Quora

std::sort uses a hybrid sorting system that switches algorithms for shorter arrays versus longer ones.

A quicksort is attempted, which of course chooses an initial partition size and a pivot.
If the partition size exceeds  2log(𝑁)
  then the potential recursion depth would be excessive and cause delays and a lot of memory, so std::sort switches to heapsort, which is done in-place and does not require recursion.
If the partition size is small (standard implementation is 16) insertion sort is used instead of quicksort for that partition, because it outperforms quicksort on most CPU architectures that have very fast cache memory.