សួស្តីជាទីស្រឡាញ់,
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.
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: