import java.util.*;

class InsertSort1
// Constructive insertion sort on a given ArrayList of integers
{
 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 an ArrayList as:");
  System.out.println(a);
  ArrayList<Integer> b=sort(a);
  System.out.println("Sorting gives the ArrayList: ");
  System.out.println(b);

 }

 public static ArrayList<Integer> sort(ArrayList<Integer> a)
 {
  ArrayList<Integer> b = new ArrayList<Integer>();
  for(int i=0; i<a.size(); i++)
     insert(a.get(i),b);
  return b;
 }

 private static void insert(Integer n,ArrayList<Integer> a)
 {
  int i;
  for(i=0; i<a.size()&&a.get(i).compareTo(n)<0; i++) {}
  a.add(i,n);
 }

}