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) $.
