import java.io.*;

class UseLists2a
{
// Demonstrates quick sort of ADT lists using 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)
 {
  List temp=List.empty();
  for(; !l1.isEmpty(); l1=l1.tail())
      temp=temp.cons(l1.head());
  for(; !temp.isEmpty(); temp=temp.tail())
      l2=l2.cons(temp.head());
  return l2;
 }

 public static List greaterThan(int n,List l)
 {
  List temp=List.empty();
  for(; !l.isEmpty(); l=l.tail())
     if(l.head()>n)
        temp=temp.cons(l.head());
  return temp;
 }

 public static List lessThanOrEq(int n,List l)
 {
  List temp=List.empty();
  for(; !l.isEmpty(); l=l.tail())
     if(l.head()<=n)
        temp=temp.cons(l.head());
  return temp;
 }

 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));
     }
 }
}