Rearrange Array in Zig-Zag Fashion

Clarify whether the requested pattern is a0 < a1 > a2 < a3... or the reverse, and whether equal values are allowed. For the usual alternating pattern, scan i from 0 to n-2. At even i, ensure a[i] <= a[i+1]; at odd i, ensure a[i] >= a[i+1]; swap the pair when the required relation fails. The key local invariant is that after fixing pair i,i+1, the relation with i-1 remains valid because the element moved into i is on the side required by the preceding comparison. This avoids sorting first, which would be O(n log n) and unnecessary for merely satisfying a zig-zag relation. If the task requires a lexicographically smallest or a specific permutation ordering, clarify because that may change the approach. Test length below two, equal values, already zig-zag input, strictly increasing, and strictly decreasing arrays. The pass is O(n) time and O(1) extra space.