<p>After sorting, invert the second half of the array:<br>
now the rest of the problem is to do a <em>perfect shuffle</em> of the array elements - a problem to come up time and again.<br>
If you want to apply a permutation in-place and know how to transform indices, you can keep a "scoreboard" of indices handled - but even a single bit per item is O(n) storage. (Find the next index still needing handling and perform the cycle containing it, keeping scores, until all indices are handled.)  </p>

<p>A pretty nice rendition of an in-place perfect shuffle in linear time and constant space in addition to the array is <a href="https://cs.stackexchange.com/a/400/19966">Aryabhata's</a> over at CS. The method has been <a href="http://arxiv.org/pdf/0805.1598v1.pdf" rel="nofollow noreferrer">placed at arxiv.org</a> by Peiyush Jain.<br>
(The complexity of the sort as a first step may dominate the permutation/shuffle step(s).)</p>

<hr>

<p>There is another interpretation of this task, or the sort step: sort into a folded array.<br>
The sort lending itself most readily to this task got to be the double-ended selection sort:<br>
In each pass over the data not yet placed, determine the min and max in 3/2n comparisons and swap into their positions, until one value or none at all is left.<br>
Or take a standard sort method, and have the indexes mapped. For the hell of it:</p>

<pre><code>/** Anything with accessors with int parameter */
interface Indexable&lt;T&gt; {
    T get(int index);
    T set(int index, T value);
//  int size(); // YAGNI?
}
/** The accessors have this folded in half,
 *   while iterator() is not overridden */
@SuppressWarnings("serial")
class FoldedList&lt;T&gt; extends ArrayList&lt;T&gt;
    implements Indexable&lt;T&gt; {
    public FoldedList(@SuppressWarnings("unchecked") T...elements) {
        super(Arrays.asList(elements));
    }
    int map(int index) {
        final int last = size()-1;
        index = 2*index;
        return last &lt;= index ? 2*last-index : index+1;
    }
    @Override
    public T get(int index) { return super.get(map(index)); }
    @Override
    public T set(int index, T element) {
        return super.set(map(index), element);
    }
}

/** Sort an Indexable&lt;T&gt; */
public class Sort {
 // Hoare/Sedgewick using middle index for pivot
    private static &lt;T extends Comparable&lt;T&gt;&gt; 
    int split(Indexable&lt;T&gt; ixable, int lo, int hi) {
        int
            mid = lo + (hi-lo)/2,
            left = lo+1,
            right= hi-1;
        T pivot = ixable.get(mid),
            l = null, r = null;
        ixable.set(mid, ixable.get(lo));
    scan:
        while (true) {
            while ((l = ixable.get(left)).compareTo(pivot) &lt; 0)
                if (right &lt; ++left) {
                    left--;
                    break scan;
                }
            while (pivot.compareTo(r = ixable.get(right)) &lt; 0)
                if (--right &lt;= left) {
                    left -= 1;
                    l = ixable.get(left);
                    break scan;
                }
            ixable.set(left, r); // place misplaced items
            ixable.set(right, l);
            if (--right &lt; ++left) {
                left = right;
                l = r;
                break;
            }
        }
        ixable.set(lo, l); // put last left value into first position 
        ixable.set(left, pivot); // place pivot at split index

        return left;
    }

    private static &lt;T extends Comparable&lt;T&gt;&gt;
    void sort(Indexable&lt;T&gt; ixable, int lo, int hi) {
        while (lo+2 &lt; hi) { // more than 2 Ts
            int split = split(ixable, lo, hi);
            if (split - lo &lt; hi - split) {
                sort(ixable, lo, split);    // left part smaller
                lo = split + 1;
            } else {
                sort(ixable, split+1, hi);  // right part smaller
                hi = split;
            }
        }
        T l, h;
        if (lo &lt; --hi // 2 Ts
            &amp;&amp; (l = ixable.get(lo)).compareTo(h = ixable.get(hi)) &gt; 0) {
            ixable.set(lo, h); // exchange
            ixable.set(hi, l);
        }
    }

    public static &lt;T extends Comparable&lt;T&gt;&gt;
    void main(String[] args) {
        Indexable&lt;Number&gt; nums = new FoldedList&lt;&gt;( //2,6,1,7,9,3);
            7, 3, 9, 3, 0, 6, 1, 2, 8, 6, 5, 4, 7);
        sort((Indexable&lt;T&gt;) nums);
        System.out.println(nums);
    }
}
</code></pre>
Searching for a better method for zig-zag array
<p>A zig-zag method which takes an array as argument and returns a zig-zag array.</p>

<p>Example : Input 2,6,1,7,9,3
          Output 9,1,7,2,6,3</p>

<p>The array returned must have alternative highest numbers and lowest numbers.</p>

<p>I can think of this method. 
//Pseudo code</p>

<pre><code>public static int [] zig-zag(int arr[])
    {
         arr.sort();
         int returnArr[] = new int[arr.length];
         int begindex = 0, endindex = arr.length -1;
         int idx = 0;
         while(begindex&lt;arr.length/2-1 &amp;&amp; endindex&gt;=arr.length/2)
         {
             returnArr[idx++] = arr[endindex];
             returnArr[idx++] = arr[begindex];
             begindex++;endindex--;
         }
         if(arr.length%2 == 1)
         reurnArr[idx] = arr[begindex];
         return returnArr;
     }
</code></pre>

<p>This method has a time complexity of O(nlogn) (because of the sort) and space complexity of O(n).
Is there any other way/algorithm so that it can do better than O(nlogn) ? or with O(nlogn) and space complexity being O(1) ?</p>

<p>There's one more method with TC O(n^2) and SC O(1). But not interested in TC of O(n^2).</p>