How to sort the Object{} properties?

Why does the Arrays.sort(Object[]) use insertion sort if the array length is less than 7?

• Arrays.sort(Object[]) applies insertion sort if the array length < 7, else it applies merge sort. Why would it do so if merge sort has O(n log n) time complexity and insertion sort has O(n^2)?

• Answer:

  The thing to remember about the big-O notation is that it omits (among other things) a constant. The running time is proportional to the value in the O, not equal to it. So the question is, is C_1O(n^2) greater or less than C_2O(n\, log\,n)? The answer, of course, depends on C_1 and C_2. For small values of n, the value of the constants dominates the equation. In a trivial case like this, remember that insertion sort is really O(1/2 n^2). For n=6, that's 18. For n log n, that's 15.5, essentially the same. For n=3, it actually crosses over: 4.7 for the merge sort, 4.5 for the insertion sort. That's before we get into implementation details: nonrecursive sorts like insertion have lower overhead.