In the Sort Times (now labeled Sort Times – Part I) post I showed code that produced results that needed some additional thoughts. I requested and obtained comments from an author and professor at an Ivy League school (now using names because I have not received a written authorization to do so). Professor, thanks for your insights and thoughts.
What I noticed was that the sort (Arrays.sort()) in the standard java.utils.* library seemed to be slower than more primitive sorts (in particular Shell sort). Following are the comments I received which are quite insightful.
“Shellsort is a pretty fast algorithm for moderate n. The difference between n log n and n^4/3 is not so great unless n is large. Moreover, n^4/3 is a worst-case bound and such worst-case inputs are hard to find”.
“I recommend timing only one algorithm per Java program. Sometimes the order in which you perform the timing tests within a Java program (e.g., call shellsort then system sort vs. call system sort then shellsort) can alter the results”.
Some edited results from the Eclipse IDE console follow:
main <<< alg1 ==>Shell<==
main <<< alg2 ==>Library<==
main <<< N: 1000000
main <<< T: 100
main <<< t1: 49026.00 ms
main <<< t2: 15855.00 ms
main <<< Library sort is 3.09 times faster than Shell sort
main <<< t1: 61504.00 ms
main <<< t2: 15291.00 ms
main <<< Library sort is 4.02 times faster than Shell sort
main <<< t1: 43924.00 ms
main <<< t2: 15164.00 ms
main <<< Library sort is 2.90 times faster than Shell sort
main <<< alg1 ==>Library<==
main <<< alg2 ==>Shell<==
main <<< N: 1000000
main <<< T: 100
main <<< t1: 15495.00 ms
main <<< t2: 48796.00 ms
main <<< Library sort is 3.15 times faster than Shell sort
main <<< t1: 15314.00 ms
main <<< t2: 44426.00 ms
main <<< Library sort is 2.90 times faster than Shell sort
main <<< t1: 15358.00 ms
main <<< t2: 46561.00 ms
main <<< Library sort is 3.03 times faster than Shell sort
With a lot less entries:
main <<< alg1 ==>Shell<==
main <<< alg2 ==>Library<==
main <<< N: 100
main <<< T: 100
main <<< t1: 17.00 ms
main <<< t2: 5.00 ms
main <<< Library sort is 3.40 times faster than Shell sort
main <<< t1: 19.00 ms
main <<< t2: 7.00 ms
main <<< Library sort is 2.71 times faster than Shell sort
main <<< t1: 18.00 ms
main <<< t2: 5.00 ms
main <<< Library sort is 3.60 times faster than Shell sort
main <<< alg1 ==>Library<==
main <<< alg2 ==>Shell<==
main <<< N: 100
main <<< T: 100
main <<< t1: 5.00 ms
main <<< t2: 15.00 ms
main <<< Library sort is 3.00 times faster than Shell sort
main <<< t1: 5.00 ms
main <<< t2: 15.00 ms
main <<< Library sort is 3.00 times faster than Shell sort
main <<< t1: 7.00 ms
main <<< t2: 18.00 ms
main <<< Library sort is 2.57 times faster than Shell sort
I fully understand that in general one should take the results of at least 
five runs, discard the fastest and slowest and average the three left. Sorry I am lazy.
You can see that the order of the sorts changes. It is in the same program but the order is randomly selected as illustrated by the following code:
/*
* test code
*/
public static void main(String[] args) throws Exception {
final String first = “Shell”;
final String second = “Library”;
final int N = 100;
final int T = 100;
String alg1 = null;
String alg2 = null;
// **** select order of sort algorithms for this run ****
if ((System.currentTimeMillis() % 2) == 0) {
alg1 = first;
alg2 = second;
} else {
alg1 = second;
alg2 = first;
}
// **** ****
System.out.println(“main <<< alg1 ==>” + alg1 + “<==”);
System.out.println(“main <<< alg2 ==>” + alg2 + “<==”);
System.out.println(“main <<< N: ” + N);
System.out.println(“main <<< T: ” + T);
double t1 = timeRandomInput(alg1, N, T);
System.out.printf(“main <<< t1: %8.2f ms\n”, t1);
double t2 = timeRandomInput(alg2, N, T);
System.out.printf(“main <<< t2: %8.2f ms\n”, t2);
if (t1 < t2) {
System.out.printf(“main <<< %s sort is %.2f times faster than %s sort\n”, alg1, t2 / t1, alg2);
} else {
System.out.printf(“main <<< %s sort is %.2f times faster than %s sort\n”, alg2, t1 / t2, alg1);
}
}
It seems that the results are similar when the order of the sorts changes (Shell then Library and Library then Shell) and when the count of elements also change (100 to 1,000,000). Most important, Library seems to perform faster (more on this later on).
“The system sort for objects is required to be stable; shellsort is not stable”.
From Wikipedia:
“Stable sorting algorithms maintain the relative order of records with equal keys (i.e. values). That is, a sorting algorithm is stable if whenever there are two records R and S with the same key and with R appearing before S in the original list, R will appear before S in the sorted list”.
By the way, the Algorithms fourth edition book by Robert Sedgewick and Kevin Wayne provides a more extensive description of stability with examples in section 2.5.
In our case at hand, stability is not an issue. The random number generator producing double values, depending on the number of entries and what else was going on in the computer, may have produced duplicate values. Different situations might require the use of stable sorting algorithms.
“The system sort is optimized not just for random arrays but also arrays with special structure (e.g., nearly sorted, reverse sorted, all equal, etc.)”.
This is another consideration that should be taken into account when choosing a sorting algorithm. The performance of different algorithms varies depending on the input values. There is a lot to think about and take into consideration when selecting sorting methods.
Finally, but in my opinion the most interesting comment follows:
“The system sort is using a version of mergesort known as Timsort—not quicksort—because you are passing objects, not primitives. It might be worth re-running the same experiment with double[] instead of Double[]”.
When one uses a double primitive, the length of the primitive is very well defined in memory and there are no foreign bytes to consider in the sort. When sorting Double objects, the size of the object may vary between implementations and versions and the actual Double object (in this case) has additional bytes which may not be included by the sort algorithm.
In addition, the Java library takes such factors into account and switches algorithms based on the argument type (e.g., double versus Double) and the size of the arrays (e.g., 100 versus 1,000,000). The libraries are open source and have been tweaked numerous times to transparently perform as well as possible.
A note from the actual library code follows:
“Implementation note: The sorting algorithm is a Dual-Pivot Quicksort by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm offers O(n log(n)) performance on many data sets that cause other quicksorts to degrade to quadratic performance, and is typically faster than traditional (one-pivot) Quicksort implementations”.
Timsort is a hybrid stable sorting algorithm, derived from merge sort and insertion sort, designed to perform well on many kinds of real-world data. It uses techniques from Peter McIlroy’s “Optimistic Sorting and Information Theoretic Complexity”, in Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 467–474, January 
1993. It was implemented by Tim Peters in 2002 for use in the Python programming language. The algorithm finds subsequences of the data that are already ordered, and uses that knowledge to sort the remainder more efficiently. This is done by merging an identified subsequence, called a run, with existing runs until certain criteria are fulfilled. Timsort is used to sort arrays of non-primitive type in Java SE 7 and other versions.
A snippet from my modified code follows:
/*
* use Java library sort
*/
// public static void sort(Comparable[] a) {
public static void sort(double[] a) {
Arrays.sort(a);
}
Following is the modified Shell sort code:
package john.canessa.sort;
public class ShellSort {
/*
* sort
*/
// public static void sort(Comparable[] a) {
public static void sort(double[] a) {
int n = a.length;
// **** 3x + 1 increment sequence: 1, 4, 13, 40, 121, 364, 1093, … ****
int h = 1;
while (h < (n / 3)) {
h = (3 * h) + 1;
}
// **** sort the array ****
while (h >= 1) {
// **** h-sort the array ****
for (int i = h; i < n; i++) {
for (int j = i; (j >= h) && less(a[j], a[j-h]); j -= h) {
exch(a, j, j – h);
}
}
// **** update h ****
h /= 3;
}
}
/*
* determine if the array is h-sorted
*/
private static boolean isHSorted(Comparable[] a, int h) {
// System.out.println(“isHSorted <<< h: ” + h);
for (int i = h; i < a.length; i++) {
// System.out.println(“isHSorted <<<< i: ” + i + ” i – h: ” + (i – h));
if (less(a[i], a[i – h])) {
return false;
}
}
return true;
}
/*
* determine if v is less than w
*/
private static boolean less(Comparable v, Comparable w) {
return v.compareTo(w) < 0;
}
/*
* exchange two elements
*/
// private static void exch(Comparable[] a, int i, int j) {
// Comparable temp = a[i];
private static void exch(double[] a, int i, int j) {
double temp = a[i];
a[i] = a[j];
a[j] = temp;
}
/*
* show
*/
private static void show(Comparable[] a) {
System.out.print(“sort <<< a: “);
for (int i = 0; i < a.length; i++) {
System.out.print(a[i] + ” “);
}
System.out.println();
System.out.print(” “);
for (int i = 0; i < a.length; i++) {
System.out.print((i % 10) + ” “);
}
System.out.println();
}
/*
* check if array is or is not sorted
*/
public static boolean isSorted(Comparable[] a) {
for (int i = 1; i < a.length; i++) {
if (!less(a[i – 1], a[i])) {
return false;
}
}
return true;
}
}
Some readers might consider this blog entry a double edged sword. On one hand it may give the impression that the study of algorithms in computer science should only be left to academia and very few practitioners. The bulk of practitioners should not care about them because the best one will automatically be used by libraries as was the case when invoking the Arrays.sort() method.
On the other hand, we have the issue of the type of data being passed. Clearly when using a double over the object Double, performance met expectations.
I am on the latter group. I always like to understand what I am doing in order to select or write the best possible code. Such characteristics are part of a whole different discipline in Computer Science know as Software Engineering.
At this point I will move on reading and experimenting with the Algorithms book.
If you have comments or questions regarding this or any other post in the blog, please do not hesitate and send me a message. Unless you explicitly state you allow me to use your name I will keep it in confidence.
John
john.canessa@gmail.com
Follow me on Tweeter: @john_canessa