sort the array and split at the midpoint. interleave from both halves, taking from the left half for even indices and right half for odd indices. this ensures the wiggle property: smaller values alternate with larger ones.
by using the larger values from the right half and smaller from the left, we guarantee that each element is properly positioned relative to its neighbors.
pattern
the interleaving pattern ensures nums[i] < nums[i+1] > nums[i+2] for all valid indices. we traverse from the middle of each half outward to maintain this relationship.
complexity
O(n log n) time for sorting, O(n) space for the sorted copy and result. the interleaving is linear.