2 ms·
there isn't a linear time algorithm, but there is an algorithm in O(n*log(n)^2) http://maths-people.anu.edu.au/~brent/pd/rpb032.pdf http://maths-people.anu.edu.
by adgjlsfhk1 4y ago
there isn't a linear time algorithm, but there is an algorithm in O(n*log(n)^2) http://maths-people.anu.edu.au/~brent/pd/rpb032.pdf http://maths-people.anu.edu.au/~brent/pd/rpb032.pdf which is pretty close. it also seems weird to have a CVE for "some algorithms don't run in linear time". should there be a 4000 element maximum for the size of list passed to sort?
- lifthrasiir 4y ago> should there be a 4000 element maximum for the size of list passed to sort? Technically speaking, yes, there should be some limit if you are accepting an untrusted input. But there is a good argument for making this limit built-in for integers but not lists: integers are expected to be atomic while lists are wildly understood as aggregates, therefore large integers can more easily propagate throughout unsuspecting code base than large lists. (Or, if you are just saying that once you have sub-quadratic algorithms you don't need language-imposed limits anymore, maybe you are right.)