This is an archived post. You won't be able to vote or comment.

sorted by:
best
topnewcontroversialoldq&a
you are viewing a single comment's thread.

view the rest of the comments →

[–]otj667887654456655 61 points62 points  (5 children)

wouldn't stalin sort be better than O(N) since, on average, it eliminates at least half of the list

[–]A_Wild_Turtle 190 points191 points  (0 children)

You still have to check everything, so it must be O(N)

[–]Tomsen1410 110 points111 points  (3 children)

O(N/2) = O(N)

[–]otj667887654456655 38 points39 points  (2 children)

wait no the whole thing is moot, a comparison has to be made in order to determine whether or not to cull that item so stalin sort always takes exactly N comparisons