Racing Java Arrays.sort with NON recursive Merge Sort implementation

Question

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 < 4){ Arrays.sort(source); return; } presort(source); int[] buffer = new int[source.length]; boolean swapBufferSource = false; for (int count = 4; count < source.length; count *= 2) { Arrays.fill(swapBufferSource ? source : buffer, 0); for (int startingIndex = 0; startingIndex < buffer.length; startingIndex += count * 2) { int leftBound = startingIndex + count; int rightBound = Math.min(startingIndex + count * 2, source.length); if (swapBufferSource) { merge(buffer, source, startingIndex, leftBound, rightBound); } else{ merge(source, buffer, startingIndex, leftBound, rightBound); } } swapBufferSource = !swapBufferSource; } if(swapBufferSource){ System.arraycopy(buffer, 0, source, 0, buffer.length); } } private static void presort(int[] source) { for (int i = 0; i < source.length - 4; i += 4) { bubleSort4(source, i); } bubleSort4(source, source.length - 4); } private static void merge(int[] source, int[] buffer, int startingIndex, int leftBound, int rightBound) { int leftIndex = startingIndex; int rightIndex = leftBound; for (int i = startingIndex; i < rightBound; i++) { if (leftIndex >= leftBound || (rightIndex < rightBound && source[leftIndex] > 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) | swap(source, 1, 2, startingIndex) | swap(source, 2, 3, startingIndex) ); } private static boolean swap(int[] source, int i, int j, int startingIndex) { if(source[startingIndex + i] > source[startingIndex + j]){ int tmp = source[startingIndex + i]; source[startingIndex + i] = source[startingIndex + j]; source[startingIndex + j] = tmp; return true; } return false; } } 

Testing program source code

Base test class

public abstract class ArraysTestBase { protected int[][] buffer; private final Random random = new Random(); public int numberOfTests = 100; public int maxValue = 1000; public int numberOfItems = 100; protected void createBuffer() { buffer = new int[numberOfTests][]; for (int i = 0; i < numberOfTests; i++) { int[] list = new int[numberOfItems]; addRandomNumbers(list); buffer[i] = list; } } protected void createBuffer(int...parametes) { buffer = new int[1][]; buffer[0] = parametes; } protected void addRandomNumbers(int[] list) { for (int i = 0; i < numberOfItems; i++) { int value = random.nextInt(maxValue); list[i] = value; } } protected int[][] cloneBuffer() { int[][] clonedBuffer = new int[numberOfTests][]; for(int i = 0; i < buffer.length; i++){ int[] clonedList = new int[buffer[i].length]; int[] list = buffer[i]; for (int j = 0; j < list.length; j++) { int element = list[j]; clonedList[j] = element; } clonedBuffer[i] = clonedList; } return clonedBuffer; } public abstract void test(); } 

Performance Test

public class ArrayPerformanceTest extends ArraysTestBase { private final Timer timer = new Timer(); public void test() { createBuffer(); timer.reset(); testSystem(); timeResoult("System"); timer.reset(); testMy(); timeResoult("My List"); } public void test(int numberOfTests) { long myTotalTime = 0; long systemTotalTime = 0; for(int i = 0; i < numberOfTests; i++){ createBuffer(); timer.reset(); testSystem(); long systemTime = timeResoult(); systemTotalTime += systemTime; timer.reset(); testMy(); long myTime = timeResoult(); myTotalTime += myTime; System.out.println("My Time / System Time = " + myTime + " / " + systemTime + " = \t" + ((double) myTime / systemTime)); } System.out.println("My Time / System Time = " + ((double) myTotalTime / systemTotalTime)); } private long timeResoult() { return timeResoult(null); } private long timeResoult(String source) { long time = timer.check(); if (source != null) { System.out.println(source + ">\tTime: " + time); } return time; } private void testMy() { int[][] buffer = cloneBuffer(); for (int i = 0; i < numberOfTests; i++) { int[] list = buffer[i]; SortMerge4.sort(list); } } private void testSystem() { int[][] buffer = cloneBuffer(); for (int i = 0; i < numberOfTests; i++) { int[] list = buffer[i]; Arrays.sort(list); } } } 

Timer

public class Timer { private long time; public void reset(){ time = System.currentTimeMillis(); } public long check(){ return System.currentTimeMillis() - time; } } 

Main

public static void main(String[] args) { ArrayPerformanceTest testBasics = new ArrayPerformanceTest(); testBasics.numberOfTests = 1000; testBasics.numberOfItems = 1000; testBasics.maxValue = 1000000; testBasics.test(1000); } 

Why this testing is not really a test

Well it's just give you the feeling weather my algorithm is really better, but to perform a true test, it need to be tested on different machines(64 bit/ 32 bit), the test need to explain when java jet is starting. The inputs need to be both equal redistributed numbers(like the random numbers in my test) and real world data. I been trying to make more serious analysis over this code but it's to complicate for me.

Answer 1

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 < offset + 3; i++) { if (source[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.

Answer 2

Algorithms

I would also like to add couple observation on top of previous answers. I was slightly confused if you were really comparing your merge sort with the Arrays.sort(int[])?? The Arrays.sort(int[]) uses a different algorithm. Tuned quick sort according to a documentation Arrays doc

So I have a feeling that you might be comparing two different algorithms.

Performance tests

Another observation that I found was that I would suggest to adjust the performance test. Firstly, for performance testing you should be using System.nanos(). System.currentMillis() dont have a milisecond precision, depends on a OS it could even have a 16ms interval of incrementing.

Try to run the tests for a different size of the array. I notice you used always 100 items. I would suggest to try more such as 1K, 10K, 100K, 1M... This gives you a overview if the 10% speed up is always there or if, for example, with 1M you only get 1%. The reason why this is good to test is if you find that the speed up decreases with higher numbers then there is some constant overhead that is not connected to a number of items in the array. Which you might want to know. On the other hand if you know that your algorithm will be run for arrays of size around hundred this is a relevant performance test that gives you relevant results.