QuickSort: comparing Java to PHP

Standard

QuickSort uses a divide and conquer technique to organize the arrays contents. The algorithm runs in:

worst case: O(n2)
best case: O(n log n) (simple partition)
or O(n) (three-way partition and equal keys)
average: O(n log n)

Motivation:

In the debate of Java vs PHP it was asked why use java when many tasks require less code in PHP. The answer while complex boils down to performance. This is a tiny example to show a performance comparison for each language.

The Algorithms

As a additional angle two separate implementations of the quicksort in Java have been added. One will use arrayLists while the other integer array. Additionally, JDK 7 / 8 will ran separately to analyze platform performance.

The PHP implementation uses a straight integer array.

Each algorithm is fed in X number of random integers. For Java to assure accuracy 50 iterations on the algorithm are performed to determine the run time. PHP is configured for 10 iterations due to the memory limit of 2 gigabytes. While one could argue that the data is inconsistent due to the randomized values, by increasing the iterations it gives a more accurate result.

Results:

I have omitted the PHP 10,000,000 array size test as is such a high number it skews the graph.

Conclusion:

JDK 7 appears to have a slight edge when it comes to arrayLists, however the difference while worth nothing does not conclude performance improvements. Therefore, Java 7 / 8 performance does not differ. As expected PHP performance is considerably worse that Java. PHP is not designed to nest over 100 functions. This can be configured as a variable as described below.

To run your own tests checkout either the PHP or Java repository on Github.

Possible errors:

PHP Fatal error: Maximum function nesting level of ‘100’ reached, aborting!

This error means that you need to increase the allowed number of nested calls. This can be configured by editing the php.ini file.

Tech Specs
Java JDK 8 / 7
PHP 5.5 (2GB memory allocated)
AMD FX 8-core
16gb RAM 1600mhz