Circles are first sorted by x using Quicksort, then scanned left to right using a sliding window of 2*R to limit the N^2 comparison loop. Comparisons for the latter part are shown in the speech bubble. The purple line is the result of the NlogN sorting by X coord, All touching circle pairs are highlighted in yellow. Failed comparisons between two circles are in green. What is not shown here are the comparisons carried out during the sorting phase (because they do not compare Euclidean distance, only x separation which is cheaper. In real life however both tests count about the same due to the fixed code overhead of Scratch)
See https://scratch.mit.edu/discuss/topic/227625/ started by Nalholigy. If looking at the code, be aware that there is some left-over code from previous (unsuccessful/abandoned!) attempts with a more complex algorithm. Although sorting in Y as well should afford an NlogN algorithm, this NlogN+N^2 has a very small k for the N^2 step and could be faster in practice - it's certainly simpler to code for very little extra runtime cost. (However in the case of very dense circle packing, this will degenerate to N^2. It works best in sparser layouts) Next improvement: a better optimisation: sort in x. then find every gap on x axis that is > 2*R. Take these separated chunks and sort them by Y. split again where there is a Y gap > 2*R. Finally do an N^2 sliding window comparison on the remaining groups as is done here. A more optimal algorithm is possible that doesn't rely on finding gaps, but the easiest implementation of it relies on duplicating circles into multiple partitions each time the set is divided, and at first glance it looks like the solution will be very heavy in memory usage, not to mention quite complex to get the code right!
