សួស្តីជាទីស្រឡាញ់,
this is a classic computer science bachelor topic: Sorting algorithms, implementing them and in the figuring out that Quicksort is the fastest you can get (by divide-n-conquer).
Hence, it amazed me to find out there is a new even faster Quicksort called Pattern defeating Quicksort, it not only uses Quicksort internally but jumps to other algorithms if suitable as well. Only downside, it only works on medium-sized data sets (as everything has to fit in RAM).
The paper this week is the initial proof of this new algorithm. Warning: It is quite mathematical as of why I also linked you a YouTube video explaining it.
Software exists to create business value
I am Simon Frey, the author of the Weekly CS Paper Newsletter. And I have great news: You can work with me
As CTO as a Service, I will help you choose the right technology for your company, build up your team and be a deeply technical sparring partner for your product development strategy.
Checkout my website simon-frey.com to learn more or directly contact me via the button below.
Abstract:
A new solution for the Dutch national flag problem is proposed, requiring no three-way comparisons, which gives quicksort a proper worst-case runtime of O(nk) for inputs with k distinct elements. This is used together with other known and novel techniques to construct a hybrid sort that is never significantly slower than regular quicksort while speeding up drastically for many input distributions.
Download Link:
https://arxiv.org/pdf/2106.05123.pdf
Additional Links: