# Segregate positive and negative integers in linear time

Given an array consisting of positive and negative integers, segregate them in linear time and constant space. Output should print contain all negative numbers followed by all positive numbers.

For example,

Input:  [9, -3, 5, -2, -8, -6, 1, 3]

Output: [-3, -2, -8, -6, 5, 9, 1, 3 ]

We can solve this problem in linear time by using partitioning logic of quicksort. The idea is to use 0 as pivot element and make one pass of partition process. The resultant array will satisfy the given constraints.

Here’s a C++ and Java program that demonstrates it:

## C++

Output:

-3 -2 -8 -6 5 9 1 3

## Java

Output:

[-3, -2, -8, -6, 5, 9, 1, 3]

The time complexity of above solution is O(n) and auxiliary space used by the program is O(1).

The problem with this approach is that it changes relative order of elements. We can also modify Merge Sort merge() function to solve this problem. The idea is while merging the left- and right- subarray, to merge in such a way that negative elements of both left- and right- subarrays are copied first followed by positive elements of left- and right- subarrays. Note that as left- and right-subarray are already sorted, negative numbers are present in beginning of both subarrays. The time complexity of this solution would be O(nlogn) and it maintains the relative order of elements.

Exercise: Modify the solution so that positive numbers will come first.

(1 votes, average: 5.00 out of 5)