Holy Grailsort: Prototyping "Smarter" Block Select Sort

Подписаться 26 тыс.

Просмотров 15 тыс.

50% 1

Massive credit to aphitorite, Anonymous0726, Taihennami, and Control for discovering an even faster variant of "block selection sort" than "smart" block select sort!
Follow our project here: github.com/Hol...
Visit our community Discord: / discord
Check out the NEW home for ArrayV here: github.com/gam...
Check out the Mother 1+2 Restoration project: / discord
Thank you to Kalmar Republic and The Marshal Star for supporting my videos!
Join this channel to get access to perks:
/ @musicombo

Опубликовано:

26 сен 2024

Ссылка:

Скачать:

Готовим ссылку...

Добавить в:

Мой плейлист

Посмотреть позже

Комментарии : 17

@Musicombo 2 года назад

Visit our community Discord: discord.gg/thestudio Check out the NEW home for ArrayV here: github.com/gaming32/ArrayV-v4.0

@deadleaves140 Год назад

Absolutely no idea as to what’s going on but it’s silly and funny :>

@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.