3 ms·
Since the sorting scene seems to be fully assembled in this thread, I take the opportunity to ask quick question about a use case that does not seem uncommon: I
by jansan 4y ago
Since the sorting scene seems to be fully assembled in this thread, I take the opportunity to ask quick question about a use case that does not seem uncommon: Is there an algorithm that is especially efficient if the array contains many sorted sequences, and still works alright for fully shuffled arrays? And are there algorithms that should be avoided in these cases.
- scandum 4y agoQuadsort, fluxsort, blitsort, and crumsort all qualify depending on your needs. skasort_cpy is pretty good on 32 bit integers if you give it n auxiliary memory. rhsort is very good and likely the best for 31 bit integers, but a bit rough around the edges still, and doesn't work well on arrays above 1M elements. Avoid radix sorts for 64 bit integers, they're ideal for 16 bit. glidesort is promising, though I haven't seen it benched against the latest fluxsort / blitsort. Timsort's main problem is that it's slow on shuffled arrays. pdqsort and other introsorts aren't good on semi-ordered data.