title: Sort Even and Odd numbers in array while maintaining order
body: <p><a href="http://www.geeksforgeeks.org/segregate-even-and-odd-numbers/" rel="nofollow noreferrer">http://www.geeksforgeeks.org/segregate-even-and-odd-numbers/</a> I was looking up interview questions and came upon this interesting one. The algorithm seems simple enough but I was wondering if it was possible to maintain the order of the even and odd numbers while still maintaining the time complexity of O(n) without using any extra space.</p>
  <p>For example</p>
  <blockquote>
  <p>input: {12, 34, 45, 9, 8, 90, 3}</p>
  <p>output: {12, 34, 8, 90, 45, 9, 3}</p>
  </blockquote>
  <p>Edit: If it's not possible without extra space, can it work with the integers only rearranged in place? As in the swaps can only occur in the array</p>