Rearrange positive and negative numbers

Separate the variants first

Ask whether positives must lead, whether zero is positive or negative, whether relative order matters, and what to do when sign counts differ. For the stable unequal-count version, scan once into positive and negative lists, then append alternately while both have entries and append the remaining list unchanged. That directly proves stability and costs O(n) time and O(n) space. If counts are guaranteed equal, use even and odd output positions instead. In-place stable alternation is substantially harder and may require rotations with worse practical cost, so do not promise it unless required. Test one sign absent, an odd length, duplicate values, zeros, and a large imbalance. State the exact output convention before coding because multiple outputs can be valid under different problem statements.