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 the 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 the 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 the 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 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..-


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...

3 Responses

  1. Ks says:

    This was asked in Microsoft

  2. lipsa patel says:

    For the brute force approach, in the explanation in figure, the last step output should be 1, 2, 3, 4, 5, 6

  3. lipsa patel says:

    Line 7 in Brute Force Approach, it should be start < mid

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d bloggers like this: