Interesting sort implementation, does not fit into usual API tough

[Tommi Prami 130]

Because of 4 way swap, highly tuned implementation could still be cool.

 

https://github.com/scandum/quadsort

 

Edited November 5, 2020 by Tommi Prami

[Arnaud Bouchez 407]

Nice to read.

But I am not sure indeed where it should be used in practice.

[Stefan Glienke 2002]

Lots of bogus and bias benchmarks

[Mahdi Safsafi 225]

3 hours ago, Stefan Glienke said:

Lots of bogus and bias benchmarks

I compiled the library myself (with some modification to support MSVC) and I run the benchmark with my own tests ... Here is some facts : 

- Unlike what was advertised, quadsort never beated qsort for generic order(I repeated the tests many time).

- Stable/unstable test gave different/closest results.

- For the rest of tests ... quadsort wins.

- I didn't see any bug yet however the weird thing I saw : The author was validating the result using quadsort !!!

[Tommi Prami 130]

13 hours ago, Mahdi Safsafi said:

- I didn't see any bug yet however the weird thing I saw : The author was validating the result using quadsort !!!

Wow...

[julkas 12]

Interesting.

BTW I use always Merge Sort and Tim Sort.

Edited November 6, 2020 by julkas

[Tommi Prami 130]

Is there good Timsort for Delphi around?

 

[Stefan Glienke 2002]

14 minutes ago, Tommi Prami said:

Is there good Timsort for Delphi around?

 

@David Heffernan and me implemented one for Spring4D - you can already check it out in the develop branch

[Lars Fosdal 1792]

I have an affection for Shell's sort - but it has a weakness as it does not preserve order for equal rows, which is easily worked around - but then again, it is not recursive and does not degrade on already sorted or partially sorted lists.

[David Heffernan 2345]

1 hour ago, Lars Fosdal said:

I have an affection for Shell's sort - but it has a weakness as it does not preserve order for equal rows, which is easily worked around - but then again, it is not recursive and does not degrade on already sorted or partially sorted lists.

Timsort is stable, and performs well on partially ordered data. It's the default sort for Python and Java.

Edited November 6, 2020 by David Heffernan

[Guest]

1 hour ago, Stefan Glienke said:

check it out in the develop branch

I noticed a strange thing,

Click Downloads then see there is "Download repository  74.5MB" , i click it and got a zipped 4.6MB file, and uncompressed is around 15MB,

Is this a bug in BitBucket ?

[julkas 12]

Another generics collection (with TimSort) - https://github.com/avk959/LGenerics

I don't know about Delphi support.

[Stefan Glienke 2002]

@Kas Ob. Not strange at all (maybe a bit misleading UI I admit), what you download there is the source of a specific commit (the lastest master, which would not contain timsort btw, surprise) - repository size includes the entire history. If you want to not use git as intended then you need to switch to the branches tab and there select one of the download options.

Edited November 6, 2020 by Stefan Glienke