Sorting easy

Parallel sorting algorithm simulator

ENEL

How to use

First select the parallel sorting algorithm (Shearsort or Schnorr-Shamir algorithm) you wish to apply by clicking on its box. Then, within the selected box, define and visualize the mesh: select its dimension by the dropdwn menu, either fill it automatically with random 0/1 values or fill in your own 0/1 values and click Show array to view. By clicking Sort, you see the algorithm running.

Why B&W

Both algorithms correctly sort every input sequence. However, all input sequences - no matter what their exact values are - can alwyas be mapped to an appropriately generated sequence of zeros and ones which are visualized here as white and black cells, respectively.

Mesh enclosures

Shearsort is a good choice for small meshes while for big meshes the algorithm by Schnorr-Shamir runs faster deploying a more sophisticated breakdown of the mesh into blocks. As you will probably notice, sometimes your mesh is embedded into a bigger one for facilitating the mesh breakdown into appropriate blocks.

About the app

This game-like interactive web app is intended to serve as assistive material for learning / training purposes regarding the study and analysis of two parallel sorting algorithms for two-dimensional meshes, i.e., the Shearsort algorithm and the '3n sort' algorithm suggested by Schnorr and Shamir.

Shearsort algorithm

Shearsort is a mesh-sorting parallel algorithm which alternately sorts rows and columns of the mesh. In particular, we sort all of the rows in odd-numbered phases (i.e., phase 1, 3, 5,...) and we sort all of the columns in even-numbered phases (i.e., phase 2, 4, 6,...). The columns are sorted so that smaller numbers move upward. The odd rows are sorted so that smaller numbers move leftward, and the even rows are sorted in reverse order, i. e., so that smaller numbers move rightward. The numbers appear in a snakelike order fast enough (i.e., after at most logN + 1 phases) regarding the total number of elements to be sorted (N). Independent rows or columns are sorted using the odd-even transposition sort algorithm.
Details can be found in F. T. Leighton, Introduction to Parallel Algorithms and Architectures, Elsevier, 1992 sections 1.6.1 and 1.6.2.

Schnorr-Shamir algorithm

For large meshes, i.e., for large sets of elements to be sorted, Shearsort is unnecessarily slow. In 1986, Schnorr and Shamir suggested an optimal parallel algorithm, often mentioned as ‘’3n‘’, for sorting meshes into snake-like row-major order requiring a number of steps which is at most 3 times the number of rows (or columns) of the mesh. The main idea lies in repeatedly sorting regions of the mesh fast before performing a sort operation on the whole mesh. To do so, time-consuming sort operations involving whole rows (or columns) of the mesh are limited while rounds of sorting in parallel smaller areas (i.e., blocks) of the mesh are induced. The ‘’3n‘’ algorithm evolves in 8 phases, 3 of which are 'expensive' (phase 2, 4 and 7) involving sorting operations on whole columns or rows, while the rest of the phases are performed fast on smaller regions of the mesh (i.e., blocks). Independent rows or columns are sorted using the odd-even transposition sort algorithm. Independent blocks are sorted using Shearsort.
Details can be found in F. T. Leighton, Introduction to Parallel Algorithms and Architectures, Elsevier, 1992 sections 1.6.1 - 1.6.3 and in C. P. Schnorr and A. Shamir, An optimal sorting algorithm for mesh connected computers, in Proceedings of the 18th annual ACM Symposium on Theory of Computing (STOC 86), ACM, pp. 255–263, 1986.

Define mesh to display