И все же непонятно - почему в массиве после сортировки ( в Вашем примере ) идет дублирование чисел?
Случайные - это понятно. Но как 8-ку какую-то перекинуть влево или вправо?
Странное задание.
Так-то - все просто.
Отсортировать по убывающей.
Идти с нулевого индекса и раскидывать в два новых массива через раз, затем слить оба массива в новый искомый или старый.
P.S.
Есть особенности по четности/нечетности размерности массива.