# Shear Sort

# Shear Sort

Shear sort is a parallel sorting algorithm for data arranged on a two dimensional mesh. It alternates between sorting rows and sorting columns. Rows are sorted in a snake like order: even rows left to right, odd rows right to left. Columns are sorted top to bottom.

This alternating pattern gradually moves small values toward the beginning of the snake order and large values toward the end.

## Problem

Given an $r \times c$ grid of values, sort all values according to snake order.

Snake order means:

```text id="j6s8tf"
row 0: left to right
row 1: right to left
row 2: left to right
row 3: right to left
...
```

## Algorithm

```text id="m9p4ct"
shear_sort(G):
    repeat O(log(r * c)) times:
        parallel for each row:
            if row index is even:
                sort row ascending
            else:
                sort row descending

        parallel for each column:
            sort column ascending

    final row sort in snake order
```

The row phase orders values within each horizontal line. The column phase moves smaller values upward and larger values downward.

## Example

For a $3 \times 4$ grid, snake order reads:

```text id="r6a2gq"
G[0][0], G[0][1], G[0][2], G[0][3],
G[1][3], G[1][2], G[1][1], G[1][0],
G[2][0], G[2][1], G[2][2], G[2][3]
```

The final grid is sorted when reading values in this order.

## Complexity

Let $n = r \cdot c$.

| measure            | value                                 |
| ------------------ | ------------------------------------- |
| phases             | $O(\log n)$                           |
| row sort work      | $r$ row sorts of length $c$           |
| column sort work   | $c$ column sorts of length $r$        |
| total work         | depends on row and column sort method |
| parallel structure | rows and columns sort independently   |

With comparison sorting for rows and columns, the total work is commonly written as:

$$
O(n \log n \log n)
$$

depending on the precise mesh model and local sort implementation.

## Correctness

The snake row ordering gives the two dimensional grid a one dimensional total order. Row sorting reduces disorder within rows. Column sorting moves smaller elements toward earlier rows and larger elements toward later rows. Repeating these phases decreases global disorder until every row and column is consistent with snake order.

After enough phases, the final row sort produces a grid whose snake traversal is globally sorted.

## Practical Considerations

* Designed for mesh connected parallel machines.
* Uses regular communication patterns.
* Rows and columns can be processed in parallel.
* Performs more work than practical general purpose sorts.
* Useful for teaching parallel sorting on processor meshes.
* The snake order avoids discontinuity between adjacent rows.

## When to Use

Use shear sort when:

* data is naturally arranged on a two dimensional mesh
* communication is cheaper along rows and columns
* regular local synchronization is desired
* studying parallel sorting networks or mesh algorithms

Avoid it for ordinary CPU sorting. Merge sort, quicksort, radix sort, and sample sort are usually more practical.

## Implementation

```python id="z2k7wp"
def shear_sort(grid, rounds=None):
    rows = len(grid)
    cols = len(grid[0])

    n = rows * cols
    if rounds is None:
        rounds = n.bit_length()

    for _ in range(rounds):
        for r in range(rows):
            grid[r].sort(reverse=(r % 2 == 1))

        for c in range(cols):
            col = [grid[r][c] for r in range(rows)]
            col.sort()
            for r in range(rows):
                grid[r][c] = col[r]

    for r in range(rows):
        grid[r].sort(reverse=(r % 2 == 1))

    return grid
```

```go id="n8f1qs"
func ShearSort(grid [][]int) {
	rows := len(grid)
	if rows == 0 {
		return
	}

	cols := len(grid[0])
	n := rows * cols
	rounds := bits.Len(uint(n))

	for round := 0; round < rounds; round++ {
		for r := 0; r < rows; r++ {
			sort.Ints(grid[r])
			if r%2 == 1 {
				reverse(grid[r])
			}
		}

		for c := 0; c < cols; c++ {
			col := make([]int, rows)
			for r := 0; r < rows; r++ {
				col[r] = grid[r][c]
			}

			sort.Ints(col)

			for r := 0; r < rows; r++ {
				grid[r][c] = col[r]
			}
		}
	}

	for r := 0; r < rows; r++ {
		sort.Ints(grid[r])
		if r%2 == 1 {
			reverse(grid[r])
		}
	}
}

func reverse(a []int) {
	for i, j := 0, len(a)-1; i < j; i, j = i+1, j-1 {
		a[i], a[j] = a[j], a[i]
	}
}
```