Holy Grailsort: Prototyping "Smarter" Block Select Sort
Вставка
- Опубліковано 10 лют 2022
- 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/HolyGrailSortProje...
Visit our community Discord: / discord
Check out the NEW home for ArrayV here: github.com/gaming32/ArrayV-v4.0
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 - Наука та технологія
Visit our community Discord: discord.gg/thestudio
Check out the NEW home for ArrayV here: github.com/gaming32/ArrayV-v4.0
Absolutely no idea as to what’s going on but it’s silly and funny :>
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.
No, because there are O(sqrt n) blocks, therefore the complexity is O(sqrt n^2) == O(n).
@@Musicombo Oh that's brilliant. But what about too many items input?
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.
@@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.
@@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.
GrailSort my favorite sort
Wikisort vibes ngl
yes
kinda cringe doesn't have the run detection yet
:doge_kek: we'll get there
Er