Stability of shear sort

user_11798621 0
Viewed 406

I come across this parallel (concurrent) sorting algorithm called shear sort. I understand that it treats a N-items list as a √N square matrix. Then, it performs row sort in alternating directions. Then, it performs column sort. It repeats until no swap occurs.

Visualisation of sorting

My question is: Is it stable?

Can anyone show me the proof of stability or correctness?

Can anyone show me the Python implementation of this?

parallel-processing python-3.x sorting
2 Answers

Here's a simple counter-example for the stability. Obviously if your algorithm for sorting the lines and columns is not stable, the full sort has no chance of being stable, so let's assume you select a stable sub-sort.

0  0  2  2
1  1  0  0
1  1  1' 2
2  2  2  2

Sort by columns :

0  0  0  0
1  1  1' 2
1  1  2  2
2  2  2  2

And a few steps later you get

0  0  0  0
1  1  1  1'
1  2  2  2
2  2  2  2

1' has been moved before other 1s, the algorithm is not stable.

Correctness is trivial :

One may assume without loss of generality that the internal sorting algorithm is as follows :

while the list is not sorted:
    select i < j such that x[i] > x[j].
    swap x[i] and x[j]

Then the whole algorithm is composed only of such swaps, therefore as there are a finite number of such i, j at the beginning, then the algorithm must terminate.

It is easy to prove that when no more swaps take place, then the whole list is sorted (compare the elements at the ends)

a < b < c < d
h > g > f > e
i < j < k < l
p > o > n > m

As no swaps take place vertically, then in particular d < e, h < i and l < m.

This also shows that you only need to sort vertically the two outermost columns. Sorting all of them will just improve performance.

chqrlie for yellow blockquotes's answer gave me an idea for an even simpler counter example :

1  0  ------>  0' 0
0' 0  columns  1  0

1 0 0 0' is sorted to 0' 0 0 1. It happens to be the smallest possible counter example, as all 2-item and 3-item lists are sorted in a stable manner.

user_100277740

The algorithm for sorting the rows and columns must be stable: otherwise an array with identical elements could be reordered, breaking stability.

This condition however is not sufficient: the shear sort as document is not stable. Here is smaller counter example:

Here is a 9 element list: A1 A2 B1 A3 A4 A5 A6 A7 A8.

All Ax elements compare equal and smaller to B1

Here is the corresponding matrix stored in the initial order:

A1  A2  B1
A5  A4  A3
A6  A7  A8

The rows are sorted horizontally in zig-zag order: no change

The columns are sorted down vertically:

A1  A2  A3
A5  A4  A8
A6  A7  B1

The rows are sorted horizontally in zig-zag order: no change, hence we are done.

The final order is A1, A2, A3, A8, A4, A5, A6, A7, B1: the relative order of the Ax elements changed.

QED

user_45932670
Related