When asked for the most efficient way to sort a million 32-bit integers in 2008, then-presidential candidate Barack Obama answered, “I think the bubble sort would be the wrong way to go.”
But people are still searching for the best possible sorting algorithms, explains Slashdot reader scandum:
Long has the conviction been held that quicksort is faster than merge sort. Timsort (derived from merge sort and insertion sort) was introduced in 2002 and while slower than quicksort for random data, Timsort performs better on ordered data.
Quadsort (derived from merge sort) was introduced in 2020 and is faster than quicksort for random data, and slightly faster than Timsort on ordered data.
Also of notice is the significant performance difference on small arrays, quadsort is on average two times faster than Timsort on data sets between 10 and 1000 elements. Quadsort achieves this performance through several optimizations spread out over 1500 lines of code that get the maximum performance out of merge sort.
Quadsort’s GitHub page explains:
After the first round of sorting a single if check determines if the four swap variables are sorted in order, if that’s the case the swap finishes up immediately. Next it checks if the swap variables are sorted in reverse-order, if that’s the case the sort finishes up immediately. If both checks fail…two checks remain to determine the final order.
of this story at Slashdot.
Source:: Slashdot