Fast in-place partitioning of sorted array into two sorted subarrays

Edit - I removed all unnecessary context explanation - too wordy and ultimately irrelevant to the problem :)

This is not homework - I've written the question like it is to ensure that all the nuances are communicated.

Given the sorted arrays:

 int[] ints =  { 0, 1, 2, 3, 4, 5, 6 };
  //this one is important - my current solution fails on this
  int[] ints2 = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
 

Note due to a clarification asked by a colleague, all that's guaranteed about these arrays is that element[n] will be less than or equal to element[n+1].

Successful operations on these will separate them into two sub arrays L and R (indicated below):

/*ints == */  { 1, 3, 5, 0, 2, 4, 6 }
               /*|> L <|  |>   R  <|*/
 
 /*ints2 == */ { 1, 3, 5, 7, 9, 0, 2, 4, 6, 8 }
               /*|>    L    <|  |>    R    <|*/
 

L contains the integers that are odd and R contains those that are even, whilst retaining the original sort-order of those elements within those subarrays.

The function will NOT resort to re-sorting the elements (a lengthy sort operation will already have been performed in advance) and it won't use a temporary array. I believe that means I'm looking for O(N) complexity and O(1) memory.

The function will be provided with the start and end elements of each sub array - i.e. the caller will know in advance how many items will fall on the left/right sides (possibly by scanning the array in advance for odd/even).

This where my code is at now - I've updated it and commented it from what was in the original post:

public void DivideSubArray(int[] array, int leftStart, int leftCount, 
   int rightStart, int rightCount)
 {
   int currentLeft = leftStart, currentRight = rightStart;
   int leftCounter = leftCount;
   int temp;
   int readahead;
   while (leftCounter != 0) {
     if ((array[currentLeft] % 2) == 0)
     {
       //remember the element we swap out
       temp = array[currentRight];
       //Set as next item on the right. We know this is the next lowest-sorted 
       //right-hand item because we are iterating through an already-sorted array
       array[currentRight++] = array[currentLeft];
       // * read ahead to see if there are any further elements to be placed
       // * on the left - move them back one by one till there are no more.
       readahead = currentLeft + 1;
       while ((array[readahead] % 2) != 0)
       {
         array[currentLeft++] = array[readahead++];
         leftCounter--;
       }
       //Now write the swapped-out item in, but don't increment our currentLeft.  
       //The next loop will check if the item is in the correct place.
       array[currentLeft] = temp;
     }
     else //this item is already in the correct place
     {
       currentLeft++;
       leftCounter--;
     }
   }
 }
 

When called as follows:

int numOdd = ints.Count(i => (i % 2) == 1);
 DivideSubArray(ints, 0, numOdd, numOdd, ints.Length - numOdd);
 

It produces the expected array for ints (and many other arrays), but not ints2:

{ 1, 5, 3, 7, 9, 0, 2, 6, 4, 8 }
 

So it partitions correctly - but swaps 3,5 and 6,4. I understand why: because in the first loop 5 is swapped to the left, then 2 is propagated over because the algorithm says that 5 is odd and should stay. I have a decision tree written out that'll fix it, but having followed it a few loops it infers that the solution is recursive.

I'm struggling to see how to get around this without running more sort operations within the sub array (don't want that), or creating temporary lists/arrays as workspace (might as well stick with my current solution instead).

I feel there must be a simple way to exploit a single 'spare' variable to swap the items - I just can't see it - I'm hoping the SO collective brain will :)

---