import java.io.*;

class UseLists3
{
// Demonstrates quick sort using ADT lists, iteration, and an
// accumulator rather than append

 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 quickSort(List l)
 {
  return quickSort(l,List.empty());
 }

 private static List quickSort(List l,List acc)
 {
  if(l.isEmpty())
     return acc;
  else
     {
      int p = l.head();
      List s = List.empty();
      List g = List.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);
         }
      l = quickSort(g,acc);
      return quickSort(s,l.cons(p));
     }
 }
}