title: Segregate Even and Odd numbers, preserve order, O(1) space， O(N) time complexity
body: <pre><code>Input  = {12, 34, 45, 9, 8, 90, 3} 
  Output = {12, 34, 8, 90, 45, 9, 3}
  </code></pre>
  
  <p>Given an array of integer, rearrange all even integer before all odd numbers, but keep their original sequence in array, using O(1) space and O(n) time complexity. </p>
  
  <p>Thought:</p>
  
  <pre><code>Algorithm: segregateEvenOdd()
  1) Initialize two index variables left and right:  
              left = 0,  right = size -1 
  2) Keep incrementing left index until we see an odd number.
  3) Keep decrementing right index until we see an even number.
  4) If lef &lt; right then swap arr[left] and arr[right]
  </code></pre>
  
  <p>But this can't guarantee the order is the same.</p>
  
  <p>What if I want to use O(1) space to solve this problem?</p>