Re:FreeBSD replaces bubblesort with mergesort on SYSINTs, re...
by GuB-42 on Tuesday August 22, 2023 @05:15PM
(#37228619)
The problem is that it is an issue in 1% of cases, and it is hard to know in advance which 1%. So either you do a proper analysis to see how many inputs you really need, or you use an algorithm that scale.
For sorting, getting a n.log(N) algorithm that doesn't break down is usually just a matter of calling a library, or writing <100 lines of code if you really can't use a library. It usually doesn't have much of a negative impact when the number of inputs is small, and it is often simpler than making a proper analysis. So, when in doubt, never use a n^2 sorting algorithm.
For sorting, getting a n.log(N) algorithm that doesn't break down is usually just a matter of calling a library, or writing <100 lines of code if you really can't use a library. It usually doesn't have much of a negative impact when the number of inputs is small, and it is often simpler than making a proper analysis. So, when in doubt, never use a n^2 sorting algorithm.