import java.util.*;

class QuickSort1a
// Constructive quick sort an ArrayList of integers which are typed in
{
 public static void main(String[] args) throws Exception
 {
  Scanner input = new Scanner(System.in);
  System.out.println("Enter some numbers (all on one line):");
  String line = input.nextLine();
  String[] numbers = line.split(" +");
  ArrayList<Integer> a = new ArrayList<Integer>();
  for(int i=0; i<numbers.length; i++)
      a.add(new Integer(numbers[i]));
  System.out.println("The numbers are stored in the ArrayList as:");
  System.out.println(a);
  ArrayList<Integer> b=sort(a);
  System.out.println("After sorting the ArrayList is:");
  System.out.println(b);
 }

 public static ArrayList<Integer> sort(ArrayList<Integer> a)
 {
  if(a.size()<=0)
     return a;
  ArrayList<Integer> smaller = new ArrayList<Integer>();
  ArrayList<Integer> greater = new ArrayList<Integer>();
  Integer pivot = a.get(0);
  for(int i=1; i<a.size(); i++)
     {
      Integer n=a.get(i);
      if(n.compareTo(pivot)<0)
         smaller.add(n);
      else
         greater.add(n);
     }
  smaller=sort(smaller);
  greater=sort(greater);
  smaller.add(pivot);
  smaller.addAll(greater);
  return smaller;
 }

}