Visit our community Discord: discord.gg/thestudio Check out the NEW home for ArrayV here: github.com/gaming32/ArrayV-v4.0
@RedstoneNguyen
2 жыл бұрын
I always have this question: Will the block selection causes the sort to be O(n^2) worst case? There will be some input where this happens.
@Musicombo
2 жыл бұрын
No, because there are O(sqrt n) blocks, therefore the complexity is O(sqrt n^2) == O(n).
@RedstoneNguyen
2 жыл бұрын
@@Musicombo Oh that's brilliant. But what about too many items input?
@Musicombo
2 жыл бұрын
That's the awesome thing about Grailsort and Holy Grail: they basically calculate the square root for any length and use that for the block lengths.
@LordControl
2 жыл бұрын
@@RedstoneNguyen very good question: so what Musicombo is trying to say here is that GrailSort sorts blocks using selectionsort, but each of these blocks has a size of order sqrt(n) this means that there are at most n/size = sqrt(n) blocks. now running selectionsort on those blocks has a complexity of O(sqrt(n)^2) comparisons and O(sqrt(n)*sqrt(n)) moves, which means this is O(n) per selection.
@RedstoneNguyen
2 жыл бұрын
@@LordControl I mean, what about when there isn't enough unique items? The buffer will be smaller. But anyway i think that it will uses lazy stable so still good.
@deadleaves140
Жыл бұрын
Absolutely no idea as to what’s going on but it’s silly and funny :>
Пікірлер: 17