NEWER VERSION: https://scratch.mit.edu/projects/420013342/ Press space or tap the stage to shuffle the list, then again to sort it. Warning: The visual will make sound This sorting algorithm can both sort a list of numbers and alphabetize a list of strings. This is not a stable sort. If you need a stable sort, I’d recommend using my merge sort implementation: https://scratch.mit.edu/projects/378893414/ This is the fastest single-script, in-place sorting algorithm I’ve seen on Scratch. My main goal when creating this was to be faster than @TheLogFather’s sorting script in most cases. This has resulted in this script being better in five major ways: 1. This script is slightly faster than @TheLogFather’s script on average when sorting large arrays, with the average case being either a list of randomly-generated integers from a uniform distribution or a list of unique uniformly-distributed integers that has been shuffled. 2. In the average case, this script is significantly faster than @TheLogFather’s script when sorting small subarrays many times. 3. This script does not experience major performance drops when sorting a list with a skewed distribution. Since @TheLogFather’s script takes the mean of two numbers to generate a pivot, the pivot will be nowhere near the median when the list has a distribution that is skewed. 4. This script is a true comparison sort, unlike @TheLogFather’s script, which takes the mean of two numbers to generate a pivot. If you only need to sort a list of numbers or a list of objects that can be compared by comparing a single number for each object, this does not matter. However, if you need to alphabetize a list of strings, this makes a huge difference: ’s script cannot sort a list of strings, whereas this script can. 5. This script has optimizations to detect a completely sorted list; ’s script does not. In practice, this should not matter very often since the optimization is only used when the entire list is sorted; if even one item is out-of-place, the sorting time will return (mostly) to normal. ’s sorting script:
