import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Random;

public class Main {

    public static void main(String[] args) throws Exception {

        Integer[] array = new Integer[10000];
        Random random = new Random();

        for (int i = 0; i < array.length; i++)
            array[i] = random.nextInt(Integer.MAX_VALUE);

        long before = System.nanoTime();
        LinkedList<Integer> linkedList = new LinkedList<Integer>(Arrays.asList(array));
        linkedList.add(-1);
        Collections.sort(linkedList, Collections.reverseOrder());
        System.out.println((System.nanoTime() - before) / 1000);

        before = System.nanoTime();
        ArrayList<Integer> arrayList = new ArrayList<Integer>(Arrays.asList(-1));
        linearInsertion(array, arrayList);
        System.out.println((System.nanoTime() - before) / 1000);

        System.out.println(arrayList.equals(linkedList));
    }


    private static void linearInsertion(Integer[] intArray, ArrayList<Integer> list) {
        for (int integer : intArray) {
            for (int i = 0; i < list.size(); i++) {
                if (integer > list.get(i)) {
                    list.add(i, integer);
                    break;
                }
            }
        }
    }
}