title: Sorting an array in O(N) time
body: <p>given an array <code>A</code> of the integers <code>1,2,3,...,N</code> and the character <code>" "</code>(space) 
  we want to sort it to be <code>[1,2,3,...,N," "]</code>, where we can only swap integers with " ", but not with each other, so <code>swap(3," ")</code> is allowed while <code>swap(1,2)</code> is not. </p>
  
  <p>My attempt at it was to denote the space be <code>"-1"</code>, and search for it in O(N) time, then go over the array again from <code>i=1</code> to <code>N+1</code> and if I see for example <code>A[2] = 7</code>, I would swap <code>A[7]</code> with <code>" "</code>, then I'd swap <code>A[2]</code> with <code>" "</code> while keeping track of <code>" "</code>'s position since It's the only way to swap, that way <code>7</code> would end up at <code>A[7]</code> ( with the exception of index shifting)
  The code I wrote is the following: </p>
  
  <pre><code>public static int[] arraySort(int[] array){
  
      int space = 0;
  
      for(int i = 0; i&lt;array.length; i++ ){
          if(array[i] == -1){
              space = i;
          }
      }
  
      for(int i = 0; i&lt;array.length; i++){
          if(array[i] != i+1 &amp;&amp; array[i] !=-1){
              swap(array, array[i]-1 , space);
              space = array[i]-1;
              swap(array, i, space);
              space = i;
          }
      }
      return array;
  }
  
  public static void swap(int[] arr, int ind1, int ind2){
  
      int temp = arr[ind2];
      arr[ind2] = arr[ind1];
      arr[ind1] = temp;
  }
  </code></pre>
  
  <p>It did work, however for input such as <code>A[7,3,5,4,6,1,2,-1]</code>
  it failed, I'm aware that I might be sending an integer to the head of the array but I can't see why it wouldn't get back out since a different number goes there then it would eventually go to its position. 
  Help? or an idea of how to fix this( while still keeping it in <code>O(N)</code> time if possible? </p>