Сжатие массива без создания подмассивов

Question

Можно ли "сжать" массив, не используя 2 подмассива? Обычно результат архивации двух массивов будет выглядеть примерно так

a1 = [1,2,3]
a2 = [4,5,6]
a3 = zip(a1, a2)
a3 == [1,4,2,5,3,6]

Тем не менее, у меня нет 2 подмассивов, и все, что мне дают, - это ввод (допустим, создание массивов в данный момент не является возможностью), и я хочу сжать массив на месте. например

a1 = [1,2,3,4,5,6]
zip(a1)
a1 == [1,4,2,5,3,6]

Мой текущий алгоритм не делает это должным образом (в результате получается последовательность, в которой первая половина упакована правильно, а вторая - в обратном)

array = [1,2,3,4,5,6,7,8]
a = array[0]
b = array[1]
i = 0, j = array.length / 2
while (i + 2 < j)
    array[i] = a
    array[i + 1] = b
    swap(array, i + 1, i + 2)
    swap(array, i + 1, j)
    i += 2, j += 1
    a = b
    b = array[i + 1]

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

Полные ответы не нужны - руководство в общем направлении является предпочтительным.

Answer 1

Прямой путь - открыть место для каждого элемента при свопе, сдвигая вправо:

void swap(int *array, int left, int right) {
     int tmp = array[right];
     while (right > left)
          array[right] = array[--right];
     array[right] = tmp;
}

Теперь вам просто нужно настроить индексы цикла:

void zip(int *array, int sz) {
     int i, j;
     for (i = 1, j = sz/2; j < sz; i += 2, ++j)
          swap(array, i, j);
}