### Author Topic: QuickSort algorithm  (Read 5959 times)

#### jj2007

• Member
• Posts: 13946
• Assembly is fun ;-)
##### Re: QuickSort algorithm
« Reply #15 on: October 09, 2020, 02:37:48 AM »

Code: [Select]
`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]`...
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=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 !

• Member
• Posts: 136
• All forms of BASIC, AutoCAD, WPF 3D, ...
##### Re: QuickSort algorithm
« Reply #16 on: October 09, 2020, 10:44:04 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 !

• Member
• Posts: 136
• All forms of BASIC, AutoCAD, WPF 3D, ...
##### v4
« Reply #17 on: October 10, 2020, 11:21:49 PM »
Corrections and performance improvements in v4. Examples also added to my first post.
« Last Edit: October 11, 2020, 05:44:21 PM by i Z ! »

#### jj2007

• Member
• Posts: 13946
• Assembly is fun ;-)
##### Re: QuickSort algorithm
« Reply #18 on: May 19, 2023, 08:36:31 AM »
Found on Quora

Quote
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.