A1, A2, A3, .... An B1, B2, ... Bn The size of the array is 2n. An Ai stays on a position 2*i -1. An Bj stays on a position 2*j.
The idea is to take a content of array's cell and put it in the place where it should stay, then you take the cell in which you put a content calculate its deserved position and so on.... There is a problem that cycles will arize in some circumctences - I think when n is an even number If you reach a cycle find first A which is not in it's place(have a variable holding the position of the last A from which you started ) and continue. The complexity without cycles is O(N), with cycles O(N) + O(N/2) = O(N) --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups-beta.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---