In my complexity sensitive application, I tried profiling the performance of Insertion sort and Java's Collections.sort() by iteratively measuring the time required to sort by both these ways.
I used below Insertion sort logic
 void applyInsertionSort(ArrayList<Integer> list0) {
    ArrayList<Integer> list = new ArrayList<>(list0);
    long startTime = System.nanoTime();
    for (int i = 1; i < list.size(); i++) {
        int eleToBeSorted = list.get(i);
        for (int j = i; j > 0; j--) {
            if (eleToBeSorted < list.get(j - 1)) {
                int temp = list.get(j - 1);
                list.set(j - 1, eleToBeSorted);
                list.set(j, temp);
            }
        }
    }
    long elapsed = System.nanoTime() - startTime;
    insSortTime.add((double) elapsed / 1000000); //Record elapsed time(Millis)
    return list;
}
In another method I used Collections.sort()
void applyCollectionsSort(ArrayList<Integer> list0) {
    ArrayList<Integer> list = new ArrayList<>(list0);
    long startTime = System.nanoTime();
    Collections.sort(list);
    long elapsed = System.nanoTime() - startTime;
    collSortTime.add((double) elapsed / 1000000); //Record elapsed time(Millis)
    return list;
}
Then I iteratively(2000 iterations) called these methods independently by shuffling the elements in original list at the end of every iteration.
 for (int i = 0; i < iterations; i++) {
        applyInsertionSort(list);
        applyCollectionsSort(list);
        Collections.shuffle(list);
 }

I have following questions
- Why in the very first iteration Collections.sort()took comparatively much longer time to sort?
- why the performance of Collections.sort()is degraded in the middle portion of the series as shown in graph, even since according to Java doc,Collections.sort()uses optimized version of merge sort offering the guranteed performance ofn logn?
