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
?