Glitch in Java's Collections.sort? First time it runs takes up to 50x as long as following times

Question

(Apologies in advance for any community-hated mistakes, this is my first post.)

I noticed something odd when writing a program for a class; the program would measure the time difference between a merge sort algorithm that I wrote and the merge sort performed by the Sort function in the Java Collections.

While testing the timer for Collections.sort() with multiple trials, I had some very strange output. The first "run" takes a notably longer time than any of the runs following it.

This is true whether I run multiple instances of the Sort class, or call the same instance multiple times. It is true whether I repeatedly call a shuffled list, ordered list, reverse ordered list, or mix them up. I've tried it on different computers/OSs, same results. Trying smaller Linked Lists sometimes makes the results seem to steadily halve for a few runs until they plateau.

I've been searching for a possible reason for why this might be happening but can't find anything. Any thoughts? I don't think it's an actual glitch so much as something I'm not taking into consideration, but even my professor had no idea what the reason might be. I've put some sample results and my relevant code below.

JDK MergeSort of shuffled list:

609 milliseconds
386 milliseconds
432 milliseconds
436 milliseconds
435 milliseconds
443 milliseconds
437 milliseconds
436 milliseconds
437 milliseconds
435 milliseconds
440 milliseconds

JDK MergeSort of ordered list:

42 milliseconds
34 milliseconds
34 milliseconds
35 milliseconds
33 milliseconds
37 milliseconds
34 milliseconds
38 milliseconds
34 milliseconds
35 milliseconds
34 milliseconds

JDK MergeSort of reversed list:

2312 milliseconds
42 milliseconds
43 milliseconds
76 milliseconds
40 milliseconds
40 milliseconds
46 milliseconds
67 milliseconds
40 milliseconds
40 milliseconds
44 milliseconds

Here's the relevant code:

import java.util.LinkedList;
import java.util.Random;

public class Sort {

LinkedList test1 = new LinkedList();

public void jdkMergeSort(LinkedList test1){
    Collections.sort(test1);
}//end jdkMergeSort

public void fillLists(){
    for(int i=0; i<1000000; i++){
        Random j = new Random();
        int k = j.nextInt(100000000);
        test1.add(k );
    }//end for loop        
}//end fillLists

public void shuffleLists(){
    Collections.shuffle(test1);
}//end makeUnsortedLists

public void sortLists(){
    Collections.sort(test1);
}//end makeSortedLists

public void reverseSortLists(){
    Collections.sort(test1);
    Collections.reverse(test1);
}//end makeReverseSortedLists

public void jdkSortTimer(){
    long start,end;

    shuffleLists();
    start = System.currentTimeMillis();
    jdkMergeSort(test1);
    end = System.currentTimeMillis();
    System.out.println("JDK MergeSort of random list: " + (end-start) + " milliseconds"); 

    sortLists();
    start = System.currentTimeMillis();
    jdkMergeSort(test1);
    end = System.currentTimeMillis();
    System.out.println("JDK MergeSort of sorted list: " + (end-start) + " milliseconds");         

    reverseSortLists();
    start = System.currentTimeMillis();
    jdkMergeSort(test1);
    end = System.currentTimeMillis();

    System.out.println("JDK MergeSort of reversed list: " + (end-start) + " milliseconds");         

}//end jdkSortTimer
}//end class