question abouut string sort

Question

i have question from programming pearls

problem is following

show how to use Lomuto's partitioning scheme to sort varying length bit strings in time proportional to the sum of their length

and algorithm is following

each record in x[0..n-1] has an integer length and pointer to the array bit[0..length-1] code

void bsort(l,u,depth)
{
  if (l>=u) return;

  for (int i=l;i<u;i++)
    if (x[i].length<depth)
      swap(i,l++);

  m=l;
  if (x[i].bit[depth] == 0) swap(i,m++);
  bsort(l,m-1,depth+1);
  bsort(m,u,depth+1);
}

I need the following things:

1. how this algorithm works
2. how implement in java?

Answer 1

It's essentially almost the same in Java. If you know Java, which I assume, this shouldn't take more than a few minutes to port. I'm sure we'd be more than happy to give you some pointers as to how the algorithm works, but I'd like to see some work from you first. Take a pencil and some paper and trace the code. That's going to be your best bet with recursion.