Wikipedia has

Here, each horizontal line represents an element of the to-be-sorted array, and each arrow represents a swap operation, such that the largest element is placed on the direction the arrow is facing. My question is: can we reverse the order of "red boxes" within a "blue box"? I.e., suppose the last blue box was instead performed in the below order:

Would the algorithm still sort the array with this change?

CodePudding user response：

No, reversing these actions will not always sort the array correctly.

For instance, just look at an array of 4 values, so that we only have this part of the image:

Now we consider what happens when we reverse the actions in the larger blue box. Let's take this example:

[4,1,2,3]

After the first phase (column) completes, we get:

[1,4,2,3]

The smaller arrows of the large blue box will bring no change (as we just verified those pairs and made swaps where needed), so the only action that is left is represented by the larger arrows, which gives this result:

[1,3,2,4]

So there's a counter example.