## News:

Message to All Guests

## QuickSort algorithm

Started by i Z !, October 04, 2020, 07:56:34 PM

#### jj2007

`mov rsi,offset array1 ; In this example, we'll usemov rdi,offset indx   ; RSI and RDI to point to bases of arrays;call the QuickSort proceduremov rcx,30 ; array of 30 elementsmov rdx,offset indxmov r8,loadValueToCmp ; load pointer to proceduremov r9, offset isItLess ; load pointer to proceduremov r10, offset isItMore ; load pointer to procedureSortAny protocall SortAny ; somewhere in here appears my stack misaligned at... message; the procs!;result in 'indx' or at [RDI]`
...
`  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`
`Res=29Res=28Res=27Res=26Res=25Res=24Res=23Res=22Res=21Res=20Res=19Res=18Res=17Res=16Res=15Res=14Res=13Res=12Res=11Res=10Res=9Res=8Res=7Res=6Res=5Res=4Res=3Res=2Res=1Res=0`

#### i Z !

Quote from: jj2007 on October 09, 2020, 02:37:48 AM

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 !

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

#### jj2007

Found on Quora

Quotestd::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.