import java.io.*;

class UseLists2
{
// Demonstrates quick sort of ADT lists using only iteration

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

 public static List append(List l1,List l2)
 {
  if(l1.isEmpty())
     return l2;
  else
     return append(l1.tail(),l2).cons(l1.head());
 }

 public static List greaterThan(int n,List l)
 {
  if(l.isEmpty())
     return List.empty();
  else 
     {
      int h = l.head();
      List r = greaterThan(n,l.tail());
      if(h>n)
         return r.cons(h);
      else
         return r;
     }
 }

 public static List lessThanOrEq(int n,List l)
 {
  if(l.isEmpty())
     return List.empty();
  else 
     {
      int h = l.head();
      List r = lessThanOrEq(n,l.tail());
      if(h<=n)
         return r.cons(h);
      else
         return r;
     }
 }

 public static List quickSort(List l)
 {
  if(l.isEmpty())
     return List.empty();
  else
     {
      int p = l.head();
      List t = l.tail();
      List s = quickSort(lessThanOrEq(p,t));
      List g = quickSort(greaterThan(p,t));
      return append(s,g.cons(p));
     }
 }
}