import java.io.*;

class UseLists6
// Uses List1 rather than List
{
 public static void main(String[] args)
 throws IOException
 {
  BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
  String str;
  List1 l1, l2;
  System.out.println("Enter a list: ");
  str = in.readLine();
  l1 = List1.fromString(str);
  l2 = quickSort(l1);
  System.out.println("Sorting the list gives: ");
  System.out.println(l2);
 }


 public static List1 quickSort(List1 l)
 {
  return quickSort(l,List1.empty());
 }

 private static List1 quickSort(List1 l,List1 acc)
 {
  while(!l.isEmpty())
     {
      int p = l.head();
      List1 s = List1.empty();
      List1 g = List1.empty();
      for(l=l.tail();!l.isEmpty();l=l.tail())
         {
          int h = l.head();
          if(h>p)
             g=g.cons(h);
          else
             s=s.cons(h);
         }
      acc = quickSort(g,acc).cons(p);
      l = s;
     }
  return acc;
 }
}