Optimize algorithm arrange an array with items with even-indexs are on left side of array, items with odd-indexs are on right side of array

Requirement: using recursion, size of array is an even...