Crash in Java Collections.sort? The first time it starts, it takes up to 50 times until the next time

Question

(I apologize in advance for any hateful hatred, this is my first post.)

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

When testing the timer for Collections.sort () with several tests, I had a very strange result. The first run takes much longer than any of the runs following it.

This is true if I run multiple instances of the Sort class or call the same instance multiple times. It is true whether I repeat the shuffled list, the ordered list, the sorted list, or mixed them up. I tried this on different computers / operating systems, with the same results. Trying smaller Linked Lists sometimes makes the results seem to steadily decrease by half in a few runs until they start to plateau.

I was looking for a possible reason why this could happen, but can't find anything. Any suggestions? I do not think that this is a real glitch as far as I do not take into account, but even my professor had no idea what the reason could be. I have provided some sample results and my corresponding code below.

JDK MergeSort 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 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 Merge :

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

:

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