# Introsort in Java

Now I have this Introsort for integer arrays. Basically, Introsort is the same algorithm as Quicksort. However, in the very first invocation of that "Quicksort", it computes an integer threshold that is logarithmic in $N$, where $N$ is the length of requested range. Whenever Introsort notices that its current recursion depth exceeds the threshold, it switches to heap sort.

Couple of questions:

1. Is the code clean enough?
2. Does naming of variables make sense?
3. Any chance for better performance?
4. Is commenting sufficient?

Introsort.java:

package net.coderodde.util.sorting;

/**
* This class implements Introsort for integer arrays.
*
* @author Rodion "rodde" Efremov
* @version 1.6
*/
public class Introsort {

/**
* Sorts the entire integer array.
*
* @param array the array to sort.
*/
public static void sort(int[] array) {
sort(array, 0, array.length);
}

/**
* Sorts a particular range {@code array[fromIndex], array[fromIndex + 1],
* ..., array[toIndex - 2], array[toIndex - 1]}.
*
* @param array     the array containing the target range.
* @param fromIndex the starting, inclusive index of the target range.
* @param toIndex   the ending, exclusive index of the target range.
*/
public static void sort(int[] array, int fromIndex, int toIndex) {
int rangeLength = toIndex - fromIndex;

if (rangeLength < 2) {
return;
}

int depth = (int)(5 * Math.log(rangeLength) / Math.log(2.0)) / 3;
sortImpl(array, fromIndex, toIndex, depth);
}

// The actual implementation.
private static void sortImpl(int[] array,
int fromIndex,
int toIndex,
int depth) {
int rangeLength = toIndex - fromIndex;

if (rangeLength < 2) {
return;
}

if (depth == 0) {
Heapsort.sort(array, fromIndex, toIndex);
return;
}

// Not deep enough, use quicksort. CLRS Chapter 7.1
int q = partition(array, fromIndex, toIndex);
sortImpl(array, fromIndex, q, depth - 1);
sortImpl(array, q + 1, toIndex, depth - 1);
}

// CLRS Chapter 7.1
private static int partition(int[] array, int fromIndex, int toIndex) {
int pivot = array[toIndex - 1];
int i = fromIndex - 1;

for (int j = fromIndex; j < toIndex - 1; ++j) {
if (array[j] <= pivot) {
int tmp = array[++i];
array[i] = array[j];
array[j] = tmp;
}
}

int tmp = array[++i];
array[i] = array[toIndex - 1];
array[toIndex - 1] = tmp;
return i;
}
}


Demo.java:

import java.util.Arrays;
import java.util.Random;
import java.util.stream.IntStream;
import net.coderodde.util.sorting.Introsort;

/**
* This class implements a demonstration of Introsort's performance as compared
*
* @author Rodion "rodde" Efremov
* @version 1.6
*/
public class Demo {

private static final int LENGTH = 5000000;
private static final int ITERATIONS = 30;

public static void main(String[] args) {
long seed = System.currentTimeMillis();
System.out.println("Seed: " + seed);
Random random = new Random(seed);

long totalArraysSort = 0L;
long totalHeapsort = 0L;

for (int iteration = 0; iteration < ITERATIONS; ++iteration) {
int[] array1 = getRandomIntegerArray(LENGTH, random);
int[] array2 = array1.clone();

int fromIndex = random.nextInt(LENGTH / 10);
int toIndex = LENGTH - random.nextInt(LENGTH / 10);

long startTime = System.currentTimeMillis();
Arrays.sort(array1, fromIndex, toIndex);
long endTime = System.currentTimeMillis();

totalArraysSort += endTime - startTime;
System.out.println("Arrays.sort in " + (endTime - startTime) +
" milliseconds.");

startTime = System.currentTimeMillis();
Introsort.sort(array2, fromIndex, toIndex);
endTime = System.currentTimeMillis();

totalHeapsort += endTime - startTime;
System.out.println("Introsort.sort in " + (endTime - startTime) +
" milliseconds");

if (!Arrays.equals(array1, array2)) {
throw new RuntimeException("Sorts do not agree.");
}
System.out.println("Arrays identical: true");
System.out.println("---");
}

System.out.println("Total Arrays.sort time:    " + totalArraysSort +
" milliseconds.");
System.out.println("Total Introsort.sort time: " + totalHeapsort +
" milliseconds.");
}

private static int[] getRandomIntegerArray(int size, Random random) {
return IntStream.range(0, size)
.map((i) -> random.nextInt(2 * size))
.toArray();
}
}


You can find Heapsort.sort here.

Total Arrays.sort time:    19050 milliseconds.
Total Introsort.sort time: 21247 milliseconds.

• Could you clarify: Are you asking about the algorithm? Or are you asking about the code? And could you please explain in your own words what the idea behind the algorithm is? Aug 13, 2015 at 8:42
• I updated the question. Aug 13, 2015 at 8:48

Well this is a fairly unusual question. You try to implement an algorithm that is supposed to be as fast as somehow possible, but your question is whether this is "clean code". Have you ever looked into something that needs to be as fast as possible (e.g. a driver for a GPU)? There's absolutely nothing clean about that. Those are optimized by hand until the last bit is set where it might have the 1 in a billion chance to run one cycle faster.

Now I'm not saying that clean code can't be fast. But this is usually not the main concern of a software engineer (I'd like to emphasize usually, because I'll be beaten to death by many developers right now.). Clean code often lives from big refactorings, creating multiple classes and hundreds of functions which make exactly clear what is supposed to happen (and when). If you do this to an algorithm like yours, it might harm its performance (e.g. because the compiler doesn't manage to inline function calls etc). On the other hand we're looking at java code ...(and once again I'm hiding under the table because all java developers are shouting at me).

But now lets take a look at your code:

Does naming of variables make sense?

array, fromIndex, toIndex, rangeLength, depth, q, pivot, i, j, tmp


Gotten lazy at the end, hm? I can live with i,j and tmp. But what really bothers me is q. Your q describes the point at which the array is split. Lets call it like that: splitIndex makes a lot more sense. (I am personally not very happy with the variable name array as it may describe a keyword in another language, but I've seen it so often that I'm just going to leave it untouched.)

Is commenting sufficient?

No idea what CLRS Chapter 7.1 is. Neither does the next reader. Or you in 2 weeks. Rest looks good to me. Just make sure every API-Function has its JavaDoc, rest is really up to you (in my eyes).

Any chance for better performance?

Can't really help you with that. There are a billion little tricks, like that decrementing is sometimes quicker than incrementing, but I am really not familiar with these.

Is the code clean enough?

int depth = (int)(5 * Math.log(rangeLength) / Math.log(2.0)) / 3;


Where does this line come from? Why 5? Ehy log(2)? Why divided by 3? Coming back to question 4. Here a comment might be appropriate. Additionally you might want to move that into its own function calculateOptimalDepth().

int pivot = array[toIndex - 1];


This is small line of code might be critical to the performance of your algorithm. There are a thousand different ways to chose a pivot-element. Why did you choose this? Move it to it's on function getPivotIndex(). You might think about adding a comment why you chose this method.

int tmp = array[++i];
array[i] = array[j];
array[j] = tmp;


These three lines of code are duplicate (not quite, but almost). What do they do? They swap 2 values in an array. Where should they be? In a method called swapValuesInArray().

At this point we realize that by refactoring that, we loose the possibility to increment i while indexing the array. That's what I mean by saying "clean code is usually not fast.".

I hope this post gave you a little insight on my point of view. Obviously there are different angles this can be looked at (I mean... I insulted like three groups of developers in this post...).

• Java method names are camelCase.
– Nic
Aug 14, 2015 at 3:37
• @QPaysTaxes upps, sorry. Have been working a lot with c++ lately. Editing it. Aug 14, 2015 at 6:21

# Avoid floating point

I have an aversion to using floating point when it isn't necessary. So I really didn't like this line:

    int depth = (int)(5 * Math.log(rangeLength) / Math.log(2.0)) / 3;


You could do this in a simpler/faster way like this:

    int depth = (int)(5 * (31 - Integer.numberOfLeadingZeros(rangeLength))) / 3;