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:
- Is the code clean enough?
- Does naming of variables make sense?
- Any chance for better performance?
- 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
* to {@link java.util.Arrays.sort}.
*
* @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.
