How Inefficient Can a Sort Algorithm Be? (2012) [pdf]

Re:How Inefficient Can a Sort Algorithm Be? (2012) [pdf] by Taniwha on Tuesday March 19, 2019 @05:15AM (#19429227)

make a linear pass through the data, if they are in order quit, otherwise swap two random entries and repeat

[ Parent | on HN ]

Re:How Inefficient Can a Sort Algorithm Be? (2012) [pdf] by martin_a on Tuesday March 19, 2019 @11:02AM (#19431422)

So, the minimum running time for this would be O(1), but can one estimate the maximum? I don't see how, but maybe I'm missing something.

[ Parent | on HN ]

Re:How Inefficient Can a Sort Algorithm Be? (2012) [pdf] by astrobe_ on Tuesday March 19, 2019 @12:20PM (#19432282)

This is known as BoZosort [1], which is said to be O(n!) on average.

[1] https://en.wikipedia.org/wiki/Bogosort

[ Parent | on HN ]

Re:How Inefficient Can a Sort Algorithm Be? (2012) [pdf] by kevinwang on Tuesday March 19, 2019 @12:51PM (#19432635)

I think it may be another factor of n slower than that

Edit: wow nevermind, I just read the paper linked to bozo sort in wikipedia. They conjecture that it's O(n!) whereas bogosort is Omega(n*n!). Wow, that's surprising!

[ Parent | on HN ]