If you partition the array with pivoting 0, all negative values appear before all other positive values. This can be done in linear time, $O(n)$.