Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Hide Buttons

Divide and Conquer – Rearrange array elements in special order

Objec­tive:  Given an array of integers of size 2n, write an algorithm to arrange them such that first n elements and last n elements are set up in alternative manner. Say n = 3 and 2n elements are {x1, x2, x3, y1, y2, y3} , then result should be {x1, y1, x2, y2, x3, y3}


A [] = {1, 3, 5, 7, 9, 2, 4, 6, 8, 10}, n= 5
Output: {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}


Brute Force:

One by one shift all the elements from second half of the array to their correct positions in the left half of the array.

Time Complexity: O(n^2)

See the explanation below-



1 2 3 4 5 6 7 8 9 10

Divide and Conquer:

  1. This solution will work only if total number of elements is in 2i So total elements are either 2 or 4 or 8 or 16 ….and so on.
  2. Total length is 2n, take n elements around middle element.
  3. Swap n/2 elements on left side from the middle element with n/2 elements on the right side from the middle element.
  4. Now divide the array into 2 parts, first n elements and last n elements.
  5. Repeat the step 2, 3 on both the parts recursively.

Time Complexity: O(nlogn)

See the explanation below



[1, 2, 3, 4, 5, 6, 7, 8]

Top Companies Interview Questions..-

Google Microsoft Amazon Facebook more..

If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.

You may also like...

  • Ks

    This was asked in Microsoft

%d bloggers like this: