Write an algorithm to arrange an array such that the largest element comes first , second largest is at the end , third largest is the second from beginning and so on.

I thought that the array could be sorted first. Then, we could use array[i]=array[2*i] for the first half of the elements, storing the values at odd positions (assuming array starts at array[0]) in a second array. Then, the stored values can be written back at the end of the first array in the reverse order.

But, here sorting is required initially and requires extra space for the second array. Could you suggest some method that is more efficient?