Shuffle to Wavy Array

Given an unordered array A[]={1,2,3,7,1,2,5}, shuffle the array matching the condition A[0]<=A[1]>=A[2]<=A[3]...A possible result would be A[]={1,7,3,5,2,2,1}

Naive Thinking:Sorting the array helps to know the put integers in order. And put the second half one by one in between of the first half. This would take O(nlogn) run time. And Sorting definitely has redundancy. It doesn't need to be all in order.

Then I came to greedy. As greedy should do it in O(n). I try to match the condition as far as I traversal. If condition fails, pick up another one afterwards. This approach is not guaranteed to be O(n) and may fail at certain point.

Then I came up with swapping, as I swapping at each position will only cost O(n) run time. I try to keep the condition as far as I traversal. If no satisfied, like A[i] < A[i+1], where the condition is A[i] >= A[i+1], swap A[i] with A[i+1]. This approach works on several examples I randomly pick up. Then I found this approach is theoretically correct.

Proof by induction:
(1) when there is only 1 number, it satisfies.
(2) when there are two numbers, at most one swap with fulfill.
(3) 1.suppose A[i-1] <= A[i],
      if A[i] >= A[i+1]
          satisfies
      else A[i] < A[i+1]
          since A[i-1] <= A[i], A[i] < A[i+1], A[i+1] is the peek of three
          swap A[i] and A[i+1]
      2. suppose A[i-1] >= A[i],
      if A[i] <= A[i+1]
          satisfies
      else A[i] > A[i+1]
          since A[i-1] >= A[i], A[i] > A[i+1], A[i+1] is the valley of three
          swap A[i] and A[i+1].
Proved.

 public class Solution{  
      public static void main(String args[]){  
           Solution s = new Solution();  
           int A[] = {1,2,2,7,3,1,5};  
           s.suffle(A);  
           for(int i = 0;i < A.length;i++)  
                System.out.println(A[i]);  
      }  
      public void suffle(int[] A){  
           for(int i = 0;i < A.length-1;i++){  
                if(i%2==0)  
                     if(A[i] > A[i+1]) swap(A, i, i+1);  
                else  
                     if(A[i] < A[i+1]) swap(A, i, i+1);  
           }  
           return;  
      }  
      private void swap(int A[], int a, int b){  
           int temp = A[a];  
           A[a] = A[b];  
           A[b] = temp;  
      }  
 }