Sorting algorithm of Arrays in Java.util package

Question

 /**
 * Sorts the specified sub-array of bytes into ascending order.
 */
private static void sort1(byte x[], int off, int len) {
// Insertion sort on smallest arrays
if (len < 7) {
    for (int i=off; i<len+off; i++)
    for (int j=i; j>off && x[j-1]>x[j]; j--)
        swap(x, j, j-1);
    return;
}

From Arrays.java line 804-814

As quoted above, it's claiming of using Insertion Sort. However, I'm taking it as Bubble Sort? Which one it's actually is, and why?

Answer 1

The quoted code is an insertion sort. A bubble sort repeatedly passes through the entire array, whereas an insertion sort sorts the first element, then the first two elements, then the first three elements, etc. You can tell because the code has two indexed loops, whereas the outer loop on a bubble sort just checks whether the whole array is in order or not.

Answer 2

This whole sorting algorithm is an optimized quick sort that use median of 3 indexed elements to get pivot element, and the code that you showed, is an optimization when the input array (or from the the recursion) is small.

Although, the quoted part is an insertion sort, no doubt.

But it is wrong just look this part of algorithm, so, using this link:

• Lines 573-577 make an insertion sort, for small input arrays.
• Lines 581-593 choice the pivot element, using median of 3.
• Lines 596-611 does the sorting using the pivot element.
• Lines 614-616 puts the partition element elements back to the middle (quick sort stuff).
• Lines 619-622 recursion of the two halves of the input array.

A good explanation about quick sort could be find at http://en.wikipedia.org/wiki/Quicksort.

Answer 3

For an already sorted array, bubble sort's outer loop only go once, but insertion's outer loop run n times (although only 1 comparison for each outer loop).

I think it's obvious that it's insertion sort.

Answer 4

Bubble sort only swaps elements located at consecutive indices.

Update: the comment in the source code might wrong :-)