Skip to main content

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(log2N) + 1 phases, where N is the number of elements to be sorted. For this reason, the algorithm has a complexity of O(Nlog2N). The pseudocode of the algorithm is presented below.

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.

img
tip

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.

img