public class lqsort
{

static cell lq(cell L)
{
  cell pivotcell;
  pivotcell = findpivot(L);
  if (pivotcell == null) return L;
  partitions parts;
  parts = partition(L,pivotcell.head);
  return
   append(lq(parts.left), lq(parts.right));
} // end lq

static cell findpivot(cell L)
{ cell answer = null;
  boolean stop = false;
  cell current = L;
  if (L != null) 
   { while ((current.tail!=null) && (!stop))
      { if (current.head > current.tail.head)
           { answer = current.tail;  // set pivot
             stop = true;
           }
        current = current.tail; 
      } // end while
   } // L!=null
  return answer;
} // end findpivot

static partitions partition(cell L, int pivot)
{  cell left = null;
   cell right = null;
   cell current = L;
   while (current != null)
    { if (current.head <= pivot)
         left = new cell(current.head,left);
       else right = new cell(current.head,right);
      current = current.tail;
    }
   return new partitions(left,right);
} // end parition

static cell append(cell L, cell M)
 { if (L == null) return M;
     else return new cell(L.head,append(L.tail,M));
 }

public static void main(String[] args)
{
  int nums = Integer.parseInt(args[0]);
  int i;  // loop counter;
  cell mylist = null;
  cell sortedlist = null;
  long start, end;

  for (i=0;i<nums;i++)
    mylist = new cell((int) (Math.random()*10000), mylist);

  start = System.currentTimeMillis();
  sortedlist = lq(mylist);
  end = System.currentTimeMillis() - start;

  for(cell cur = sortedlist;cur != null;cur = cur.tail)
    System.out.print(cur.head + " ");
  System.out.print("\n");
  System.out.println("time to lqsort ~= " + end + "ms");
} // end main

} // end class lqsort

class partitions
{ cell left;
  cell right;  // left and right parititions
  partitions(cell l, cell r) { left=l; right = r; }
}

class cell 
{ 
  int head;
  cell tail;
  public cell(int h, cell t)  { head = h; tail = t; }
} // end class cell