First loop slower in performance test

I wanted to see first hand how certain data structures behave. I started with ArrayList and populated it with objects of a custom class. But when I was playing around with it I noticed that running test method X on top it is performing much slower or if I do the same job twice the second time is up to 6 times faster.

Here are some examples:

private void generateItems(int amount)
{
    System.out.println("Populating list with " + amount + " items...");
    long time = System.nanoTime();
    for (int i = 0; i < amount; i++)
    {
        items.add(new Item("Type", "Subtype", random.nextInt(width), random.nextInt(height)));
    }
    System.out.println(timePassed(time) + " List size: " + items.size());
}

private void sortList(int x, int y)
{
    System.out.println("Sorting list...");
    long time = System.nanoTime();
    Collections.sort(items, new ItemComparator(x, y));
    System.out.println(timePassed(time) + " List sorted.");
    System.out.println("First: " + items.get(0));
}

Now let's run these two methods two times:

    items = new ArrayList<>();
    generateItems(100000); //33ms
    sortList(0, 0); //118ms

    items = new ArrayList<Item>();
    generateItems(100000); //5ms
    sortList(0, 0); //28ms

I understand when I sort an already sorted list would take less time because the computer gets better at gambling the outcome but here I generate two completely random lists.

I some more methods involving iteration and conditional item retrieval and they all behave the same: the first one is much slower then if it would run later.

In order to proceed with my tests on other data structures I want to know more about this behavior. Perhaps I'm doing something wrong here or is the outcome expected and why? How do I make somewhat reliable tests like these?