About the app
An interactive animated visualization of the Shearsort parallel sorting algorithm for 2D meshes, intented to support courses on parallel algorithms.
How to use
Select your desired mesh-dimension. You can modify the generated mesh by clicking on its cells to alter their value from black to while and vice versa. Select "Sort" to watch the mesh being gradually sorted by Shearsort. Select "" to view the sorting procedure in a step-by-step fashion. "Reset" generates a new instance.
How it works
Shearsort sorts the mesh by alternately sorting rows and columns. Rows are sorted in odd phases (i.e., 1, 3, 5,...). Columns are sorted in even phases (i.e., 2, 4, 6,...). In columns smaller numbers move upward. In odd rows smaller numbers move leftward while in even rows smaller numbers move rightward. The numbers appear in a snakelike order fast enough i.e., after at most logN + 1 phases for a mesh of N numbers. The odd-even transposition sort parallel algorithm is used for sorting independent rows or columns. For details: F. T. Leighton, Introduction to Parallel Algorithms and Architectures, Elsevier, 1992.
Why black and white boxes
Shearsort correctly sorts all input sequences, which - regardless of their particular values - can always be mapped to appropriately generated equivalent sequences of 0s and 1s visualized as black and white cells.