Racing Java Arrays.sort with NON recursive Merge Sort implementation

I found a bit better implementation for Java Arrays.sort(int[]). To make this code review more simple I divide this questions to several parts.

The goal of this question is to find more ways to increase the performance even better.

Edit: Tested over Java 6, win 64 bit. In average for equal redistributed input(did not tested any other) my algorithm perform 10% better than Java native.

• How my algorithm is different from traditional merge sort

• How does my algorithm work

• Algorithm source code in Java.

• Testing program source code

• Why this testing is not really a test

How my algorithm is different from traditional merge sort

While the traditional merge sort start by dividing the the input array to half and half and half... Until reaching the bounds of 2 and than starting to merge all the half together. I did the opposite, I started from the smallest piece of the array and merge my way up. Also I have a special case of array with 4 elements.

How does my algorithm work

Read input to array.
Dividing the array to pieces of 4, and sort them all. 
Take the last 4 elements from the array and sort them.
Iterate over count from 0 to array size, multiply it by 2 in each iteration.
   iterate over startingIndex from count to array size, increase it's size by count over each iteration.
       merge the two pieces of the array. From startingIndex to startingIndex + count, and from startingIndex + count to startingIndex + 2 * count.
       Note that the second part could exceed the array size.

Algorithm source code in Java.

```
public class SortMerge4 {
public static void sort(int source[]) {
if(source.length = leftBound || (rightIndex source[rightIndex])) {
buffer[i] = source[rightIndex++];
}
else {
buffer[i] = source[leftIndex++];
}
}
}

private static void bubleSort4(int[] source, int startingIndex) {
while (swap(source, 0, 1, startingIndex) |

This is a lot of code, and I can't cover it all. But I have a few observations:

Your code is practically undocumented. Even for private methods, a short explanation would be useful. Especially when implementing a sorting algorithm, the documentation should also state algorithmic complexity guarantees – it would be very helpful to state that merge is O(rightBound - startingIndex) time and O(1) memory. In highly optimized, very clever code, I'd expect almost as much documentation as actual code.

Now a focussed review on bubleSort4:

bubleSort4 should be bubbleSort4. Spelling is important.

Let's look at your code:

private static void bubleSort4(int[] source, int startingIndex) {
    while (swap(source, 0, 1, startingIndex) | 
            swap(source, 1, 2, startingIndex) |
            swap(source, 2, 3, startingIndex)
            );
}

This body-less while is quite unusual and why this is done isn't exactly obvious. The use of bitwise-or | instead of logical-or || is another subtle detail that really should be explained in a comment.

The code could be made clearer by actually providing an empty body. I would also put the | at the front of each line:

while (   swap(source, 0, 1, startingIndex)
        | swap(source, 1, 2, startingIndex)
        | swap(source, 2, 3, startingIndex)
) {
    // empty
}

However, I would probably use a do-while loop instead:

boolean changed;
do {
    changed = false;
    changed |= swap(source, 0, 1, startingIndex);
    changed |= swap(source, 1, 2, startingIndex);
    changed |= swap(source, 2, 3, startingIndex);
} while (changed);

This code makes it much more obvious

• why the loop will execute at least once,

• what the combined return values of swap mean, and

• why we should use | instead of ||.

We could now also inline swap:

/* Bubble-sort the four elements in "source" starting at "offset".
 * The calling code has to make sure that "source.length - offset > 4".
 * Because this runs on fixed-sized input, it will run in O(1) time.
 */
private static void bubbleSort4(final int[] source, final int offset) {
    boolean changed = true;
    while (changed) {
        changed = false;

        // swap the three pairs 0-1, 1-2, 2-3 starting from "offset"
        for (int i = offset; i  source[i + 1]) {
                int tmp = source[i];
                source[i] = source[i + 1];
                source[i + 1] = tmp;

                changed = true;
            }
        }
    }
}

Note that this is the only use of swap, and that this inlining actually reduces overall complexity. Note that the bitwise-or has now been completely removed. The magic number 3 is explained by a comment.

StackExchange Code Review Q#46444, answer score: 4