https://turbowarp.org/1368240020/fullscreen?fps=60&turbo&limitless&hqpen thanks to changing rendering to perform better but look worse you can now have hqpen and turbo mode at the same time an implementation of block merge sort. grailsort was originally created by Andrey Astrelin (RIP) otherwise known as mrrl. his code was really messy, check here to see https://github.com/Mrrl/GrailSort/blob/master/GrailSort.h because of this, the holy grailsort project has rewritten grailsort in different languages to be easier to read, this project is copying off of Amari Calipso's python implementation - https://github.com/HolyGrailSortProject/Rewritten-Grailsort/blob/master/Python/Amari%20Calipso's%20Rewritten%20Grailsort%20for%20Python/GrailSort.py grailsort is called this because it is the holy grail of sorting algorithms - stable inplace and nlogn worst case time complexity. it is essentially a variation of iterative merge sort that instead of using an external auxiliary array for merging it uses a section carved out of the internal array as an internal buffer for both merging and for tagging (which is something to do with block rearrangement). it takes unique elements and uses them for the buffer. if it cant find enough, it either uses more rotation based merging or switches to lazy stable sort which is just iterative mergesort using rotation based (grailsort calls it lazy) merging. tags are used to preserve stability and to tell which block is originally from the left run or right run when merging. it rearranges blocks using pretty much selectionsort on blocks instead of individual items and using tags to preserve stability. it starts by extracting the buffer, building sorted runs, then once the runs get too big, it switches to block merging. it has a lot of fallbacks for if it doesnt have enough unique buffer items and i dont know all of them no i dont understand it this is pretty much the extent of what i understand this is really annoying to implement because 1: scratch is just bad in general 2: scratch is really slow and laggy 3: the editor is buggy 4: it uses 1 indexed arrays for some reason everything else uses 0 because it makes more sense when looking at how arrays are stored in memory. this means first item of array in nearly any popular programming language (python, rust, c++, c, c#, java, js, go etc...) is index 0 but in scratch its 1 which makes it really annoying to translate python into scratch 5: no local variables 6: no returns 7: no static typing (well there are booleans but only for function arguments) 8: you cant edit function arguments inside the function you have to make a new variable and edit that 9: organisation i could go on i put the small helper functions compare swap blockswap and rotate in different sprites for organisation purposes its probably a bit laggier tho stable not adaptive space - O(1) inplace time compl - O(nlogn) dynamic buffer (sqrtn space complexity) version:
