The workings of collision sort are best explained in my published workshop papers and posters, available from the essay page. The basic idea is pretty simple: represent data as particles in a space, but bias their collison behavior to reduce entropy: collisions are comparisons. This makes for a spatially distributed system which only ever needs to process local information. One nice property is that we can sort along multiple axes simultaneously. You can get the NetLogo demo from my software page. These animations show the 2D version of collision sort.
First, the original version, in RoarVM SmallTalk running on a 16-core machine:
(Or, here’s a MOV download.)
And here’s the NetLogo version from my RACES workshop talk:
(Or, a MOV download.)