# Shear Sort

Another example of a sorting algorithm designed for multi-processor systems where each processor is connected to only a portion of the other processors is **shear sort** (also known as **row-column sort** or **snake-order sort**). It assumes that we are working with processors connected in a matrix-like form. In this setup, a processor can communicate with neighbors to the left, right, above, and below. If we imagine that processors are arranged in a matrix, the two phases of the shear sort algorithm are as follows:

- Sort the matrix rows so that even rows have values sorted in ascending order, and odd rows have values sorted in descending order.
- Sort the columns in ascending order.

It is guaranteed that the algorithm will sort the numbers in at most **sup(log ^{2}N) + 1** phases, where N is the number of elements to be sorted. For this reason, the algorithm has a complexity of

**O(Nlog**. The pseudocode of the algorithm is presented below.

^{2}N)`function shearSort(matrix) {`

for (k = 0; k < ceil(log2(matrix.lines * matrix.columns)) + 1; k++) {

for (i = 0; i < matrix.lines; i++) {

if (i % 2 == 0)

sortAscendingLine(i);

else

sortDescendingLine(i);

}

for (i = 0; i < matrix.columns; i++) {

sortAscendingColumn(i);

}

}

}

A graphical representation of how shear sort works is shown in the figure below.

At the end of the algorithm's execution, the list of numbers will be sorted in a "snake-like" manner, hence the name of the algorithm. This can be observed in the image below.