Sorting Array by Reversing Around the Middle

Sorting Array by Reversing Around the Middle is a greedy/symmetry puzzle. The only operation allowed is reversing a chunk around the center of the array, and the question is whether such reversals can ever leave the array sorted. The whole problem collapses to a simple symmetry check.

The slow way first

You could try to simulate reversals — pick a center-symmetric window, reverse it, and search for a sequence that ends sorted. But the number of reversal sequences explodes, and most lead nowhere. Brute-force search over operations is exponential and tells you nothing about why an array works.

The question to ask: what does a center reversal actually preserve? Reversing around the middle only ever swaps an element at position i with its mirror at n-1-i. It never breaks a pair apart — it just exchanges the two members of a mirror pair.

The idea: check the mirror pairs

Because every allowed move only swaps i with n-1-i, the multiset of each mirror pair never changes. For the final array to be sorted (and for these moves to even be capable of producing it), the two members of each mirror pair must be equal — otherwise the pair is stuck holding two different values that the operation can only swap, never fix.

So the answer is: walk a pointer i in from the left and j in from the right. If a[i] != a[j] for any pair, return False. If all pairs match, return True.

The key insight: a center reversal is just a mirror swap, so sortability reduces to "is the array already mirror-symmetric in value?"

Walk through it

Step through the animation. Pointer i starts at the far left, j at the far right, and they close toward the center. Each step compares one mirror pair. Pairs (0,4) and (1,3) both match, the pointers meet at the lone middle element, and we return True.

Pseudocode

i = 0, j = last index
while i < j:
    if a[i] != a[j]:
        return False         # this mirror pair can never be fixed
    i = i + 1
    j = j - 1
return True                  # every mirror pair matched

The Python solution

def can_sort_by_center_reversal(a):
    i, j = 0, len(a) - 1
    while i < j:
        if a[i] != a[j]:
            return False
        i += 1
        j -= 1
    return True

• i, j = 0, len(a) - 1 sets the two pointers at the ends.
• while i < j runs until they cross or meet — a lone middle element needs no check.
• Line 4 is the heart: a[i] != a[j] tests one mirror pair. A single mismatch kills it.
• i += 1; j -= 1 steps both pointers inward by one.
• If we exit the loop with no mismatch, every mirror pair matched, so we return True.

Complexity

We touch each element at most once and store only two indices, so it is O(n) time and O(1) space.

When this pattern shows up

Practice