0

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);
 }

enter image description here

I have following questions

  1. Why in the very first iteration Collections.sort() took comparatively much longer time to sort?
  2. 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 of n logn?
user1612078
  • 555
  • 1
  • 7
  • 22
  • 1
    [How do I write a correct micro-benchmark in Java?](http://stackoverflow.com/questions/504103/how-do-i-write-a-correct-micro-benchmark-in-java) – resueman Apr 14 '15 at 15:08
  • Don't you want to shuffle the list before `Collections.sort ` as well? – Paul Boddington Apr 14 '15 at 15:09
  • Shouldn't this: `applyInsertionSort(list); applyCollectionsSort(list); Collections.shuffle(list);` be this: `Collections.shuffle(list); applyInsertionSort(list); Collections.shuffle(list); applyCollectionsSort(list);` (As is, you are tryin to sort a sorted array)? – npinti Apr 14 '15 at 15:11
  • @npinti No. In method body, I am creating a new list everytime. – user1612078 Apr 14 '15 at 15:14
  • If I am understanding your code, what you have are multiple pointers looking at the same memory location which in the end resolves to the same list. – npinti Apr 14 '15 at 15:15
  • @npinti Well, I even tried copying individual element from the original list to the method specific private list and then applied sorting. Also I put `Collections.shuffle()` in between two method calls, but even then I got similar results. – user1612078 Apr 14 '15 at 15:26
  • @pbabcdefp I tried that as well, but I got the similar behavior. No change. – user1612078 Apr 14 '15 at 15:27
  • Ah I see. You're never actually sorting `list`. Apologies. `Collections.sort` has worst case time complexity `O(n log n)` whereas for your sort algorithm it's `O(n^2)`, so for larger and larger lists `Collections.sort` will win. – Paul Boddington Apr 14 '15 at 15:28

0 Answers0