Member-only story
🏊 Rust’s Glidesort Is 4x Faster On Random Data
The newly announced Glidesort occurs to be up to 4x faster on random data. Let’s check what is the fuzz about!
Are you tired of slow-sorting algorithms that can’t handle large datasets? Look no further than Glidesort in Rust!
This innovative algorithm combines the best features of multiple algorithms to provide blazing-fast sorting speeds and stable results, even on datasets with many duplicates. Read on to learn how Glidesort can revolutionize your sorting needs.
🤔 What Is Glidesort?
Glidesort is a stable sorting algorithm that uses a combination of Timsort-style merge sorts and pattern-defeating quicksort. It is able to take advantage of the best-case behavior of Timsort-style merge sorts for pre-sorted data, while also leveraging the best-case behavior of pattern-defeating quicksort for data with many duplicates. This makes Glidesort a versatile and efficient algorithm for a wide range of data sets.
For sorting n elements with k distinct values Glidesort has the following characteristics by default:
Glidesort can use up to the same amount of memory as the number of elements being sorted (n), or as little extra memory as you want. If you don’t provide much extra memory, the algorithm will be less efficient and take longer to sort the data. In this case, the average and worst-case time complexity become O(n (log n)²). However, in practice, the performance of Glidesort is generally good for most datasets, except when the ratio of data size to auxiliary space is extremely skewed.
By default, Glidesort allocates up to n elements worth of memory, unless this exceeds 1 MiB. In that case, it will scale down to…
