Segregate positive and negative integers in linear time

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

For example,


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


arr = [-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.

C++ implementation –

Download   Run Code


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

Time complexity of above solution is O(n).
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 Mergesort 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.

Thanks for reading.

Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂