CareerCup

You need to swap 1 by 1, 2 by 2, 4 by 4, 8 by 8 and so on.
If you use shifting strategy it take O(n^2), using this strategy it takes O(n log n).
a0 a1 a2 a3 a4 a5 a6 a7 b0 b1 b2 b3 b4 b5 b6 b7
(a0) (a1) (a2) (a3) (a4) (a5) (a6) (a7) (b0) (b1) (b2) (b3) (b4) (b5) (b6) (b7)
(a0 b0) (a2 b2) (a4 b4) (a6 b6) (a1 b1) (a3 b3) (a5 b5) (a7 b7)
(a0 b0 a1 b1) (a4 b4 a5 b5) (a2 b2 a3 b3) (a6 b6 a7 b7)
(a0 b0 a1 b1 a2 b2 a3 b3) (a4 b4 a5 b5 a6 b6 a7 b7)
(a0 b0 a1 b1 a2 b2 a3 b3 a4 b4 a5 b5 a6 b6 a7 b7)

You need to swap 1 by 1, 2 by 2, 4 by 4, 8 by 8 and so on.
If you use shifting strategy it take O(n^2), using this strategy it takes O(n log n).
a0 a1 a2 a3 a4 a5 a6 a7 b0 b1 b2 b3 b4 b5 b6 b7
(a0) (a1) (a2) (a3) (a4) (a5) (a6) (a7) (b0) (b1) (b2) (b3) (b4) (b5) (b6) (b7)
(a0 b0) (a2 b2) (a4 b4) (a6 b6) (a1 b1) (a3 b3) (a5 b5) (a7 b7)
(a0 b0 a1 b1) (a4 b4 a5 b5) (a2 b2 a3 b3) (a6 b6 a7 b7)
(a0 b0 a1 b1 a2 b2 a3 b3) (a4 b4 a5 b5 a6 b6 a7 b7)
(a0 b0 a1 b1 a2 b2 a3 b3 a4 b4 a5 b5 a6 b6 a7 b7)

public static void changeArray(String[] arr){
		if(arr.length ==0)
			return;
		int index = arr.length / 2;
		while(index < arr.length){
			String temp = arr[index];
			int counter = index -1;
			while(counter >= 0 && LessThan(arr[counter],temp)){
				arr[counter+1] = arr[counter];
				counter--;
			}
			arr[counter+1] = temp;
			index++;
		}
	}
	private static boolean LessThan(String a, String b){
		return Integer.valueOf(b.charAt(1)) < Integer.valueOf(a.charAt(1));
	}

public static void changeArray(String[] arr){
		if(arr.length ==0)
			return;
		int index = arr.length / 2;
		while(index < arr.length){
			String temp = arr[index];
			int counter = index -1;
			while(counter >= 0 && LessThan(arr[counter],temp)){
				arr[counter+1] = arr[counter];
				counter--;
			}
			arr[counter+1] = temp;
			index++;
		}
	}
	private static boolean LessThan(String a, String b){
		return Integer.valueOf(b.charAt(1)) < Integer.valueOf(a.charAt(1));
	}

public static void rearrange(int[] arr) {
    if (arr == null || arr.length % 2 == 1) return;

    int currIdx = (arr.length - 1) / 2;
    while (currIdx > 0) {
        int count = currIdx, swapIdx = currIdx;

        while (count-- > 0) {
            int temp = arr[swapIdx + 1];
            arr[swapIdx + 1] = arr[swapIdx];
            arr[swapIdx] = temp;
            swapIdx++;
        }

        currIdx--;
    }
}

O(n) solution would be something as follows:
for each even element a_i in a, do the following:
index=i
while index <n : index=index*2-1
swap (a_index, b_(i/2))
while index !=i : swap (a_index,a_((index-1)/2)); index=(index+1)/2
Repeat for array b(1..n/2) b(n/2+1)
Total operations: n+n/2+n/4...=O(n)

>>> sl
['a0', 'a1', 'a2', 'b0', 'b1', 'b2']

>>> sl.sort(key=lambda x: x[1])

>>> sl
['a0', 'b0', 'a1', 'b1', 'a2', 'b2']

Simple O(N^2) solution is just a rotation in a loop:

template<class It>
void aabb_to_abab(It first, It last)
{
	assert((last - first) % 2 == 0);
	for (auto n = last - first; n > 2; n -= 2)
		std::rotate(first + n / 2 - 1, first + n / 2, first + n - 1);
}

More involved O(N) solution is based on the decomposition of the permutation into cycles (this resembles the dolphin algorithm for array rotation). We don't know the number of cycles in advance, hence we have to count the number of elements left to process (the first and the last elements form cycles by themselves).

template<class It>
void aabb_to_abab(It first, It last)
{
	assert((last - first) % 2 == 0);

	auto n_left = last - first - 2;
	const auto n = (last - first) / 2;
	auto start = n;

	while (n_left > 0)
	{
		auto curr = start;
		auto hole = std::move(*(first + curr));
		while (true)
		{
			--n_left;
			const auto next = curr / 2 + n * (curr % 2);
			if (next == start)
				break;
			*(first + curr) = std::move(*(first + next));
			curr = next;
		}

		*(first + curr) = std::move(hole);
		++start;
	}
}

#include<stdio.h>
#include<conio.h>
int main()
{
}