/**
 * reorder.h 
 *   A variant of the infamous partition function from Quicksort.
 */

#include "reorder.h"

int
reorder (int a[], int size, int splitter)
{
  int ub; // An index for the elements that are > splitter
  int lb; // An index for the elements that are <= splitter
  int temp;

  // Idea: We try to keep thigns consistent that
  //   For all i, 0 <= i < lb, a[i] <= splitter
  //   For all j, ub < j < size, a[j] > splitter
 
  lb = 0;
  ub = size - 1;
  
  while (1)
    {
      // Keep retreating ub until we hit something small or lb == ub
      while ((lb <= ub) && (a[ub] > splitter))
        ub--;
      // At this point, we know that a[ub+1] > splitter and either
      //   a[ub] <= splitter or ub < lb.
      // Keep advancing lb until we hit something large or lb == ub
      while ((lb <= ub) && (a[lb] <= splitter))
        ++lb;
      // Let's see, 
      //   a[ub+1] > splitter
      //   a[lb-1] <= splitter
      // So, if lb > ub, we're done
      if (lb >= ub)
        return ub+1;
      // If not, we can swap and move on
      temp = a[lb];
      a[lb] = a[ub];
      a[ub] = temp;
    } // while (1)
} // reorder