Move Negative Numbers First in C++: In-Place Partition

To partition an array so negative values come first and non-negative values come after, use two indexes moving toward each other. This is a partitioning problem, not a full sort: the relative order inside either group is not preserved.

In-place two-pointer solution

#include <algorithm>
#include <vector>

void negatives_first(std::vector<int>& values) {
    std::size_t left = 0;
    std::size_t right = values.size();

    while (left < right) {
        while (left < right && values[left] < 0) ++left;
        while (left < right && values[right - 1] >= 0) --right;
        if (left < right) std::swap(values[left], values[right - 1]);
    }
}

How it works

left stops on a value in the wrong group for the front; right - 1 stops on a negative value in the wrong group for the back. Swapping fixes both positions. Each pointer moves in one direction only, so the algorithm is O(n) time and O(1) extra space.

Zero and stability

This version treats zero as non-negative. Change the comparison if your specification treats zero differently. If the original order of negative and non-negative values must remain intact, use a stable partition or an auxiliary output array; that is a different time/space trade-off.

Reference: std::partition and std::stable_partition.