Take the 2-minute tour ×

Segregating an array for even and odd numbers This is the duplicate but there is no solution which could preserve the order of the elements , is there such a solution in O(n) time and O(1) space .

I can just think of the approach which is mentioned in the duplicate link given aove

share|improve this question

1 Answer 1

I doubt it.

You could use the basic two-pointer solution shown in the linked article, but instead of swapping on odd elements you could slide array elements to the left and put the odd element in its place; that's O(n^2) time and O(1) space in the same way as insertion sort, as you have to visit each element and potentially slide it the entire length of the array.

Or you could preserve the O(n) time but use O(n) space by making two passes through the input array, copying even elements to an output array on the first pass and odd elements on the second pass.

But I don't see a way to preserve both O(n) time and O(1) space.

If instead you want all the elements sorted in their even and odd partitions, you could use the standard system sort and a comparison function that is less-than only if the lower-indexed element a is even and the higher-indexed element b is odd or if both elements have the same parity and a<b; in C that's (a%2==0 && b%2==1) || (a%2==b%2 && a<b). That's O(n log n) time and O(log n) space for the stack in the sort, so it doesn't preserve either the time or space bounds of the original, and also doesn't solve the requested problem.

share|improve this answer

Your Answer


