title: Given an array consisting of even and odd numbers. Sort the array with even first and then odds. The order of numbers can't be changed
body: <p>If the input array is - 1,4,3,8,6,5,7  the output should be - 4 8 6 1 3 5 7</p>
  
  <p>I have one solution with insertion sort kind of thing. </p>
  
  <pre><code>void sortarrayinorder(int arr[],int size)
  {
       int i,j,tem,k;
       for(i=1;i&lt;size;i++)
       {
         for(j=0;j&lt;i;j++)
         {
         if((arr[j]%2)!=0 &amp;&amp; (arr[i]%2)==0)
         {
           tem=arr[j];
           arr[j]=arr[i];
           for(k =i;k&gt;j;k--)
             arr[k]=arr[k-1];
  
             arr[k+1]=tem;
             }
           }
       }     
  }
  </code></pre>
  
  <p>Can this problem be solved in a better way? The complexity of my solution is o(n2). Please provide a solution with lesser time complexity. No extra space is allowed.</p>