Sort one sequence by O(n) in time and O(1) in space

[Asaf Las]

On Sunday, February 9, 2014 2:13:50 PM UTC+2, Wesley wrote:
> Hi guys,
>    Here is one question related to algorithm.
> Details here:
> 
> here is input sequence like a1,a2,...,an,b1,b2,...,bn ，the ax and bx always exist in pair. So, now, how to change the sequence to a1,b1,...,an,bn, with time complexity as O(n) and space as O(1).
> 
> Any comments will be appreciated.
> 
> Thanks.
> 
> Wesley

if space O(1) is needed they don't have to be merged - list alike class keeping series as members returning a[i] if i is odd and b[i] if i is even would be enough. then constructing such sequence (or class instance) will be done in O(1) as well.

/Asaf