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.

public static void quickSort(ArrayList<Integer> array, int start, int end) { // Align the left and right starting positions int leftPos = start; int rightPos = end; // if there is only one element in the partition, do not do any sorting if ((end - start) < 1) { return; } int pivot = array.get(start); // keep scanning because the left and right indecies have not met while (rightPos > leftPos) { while (array.get(leftPos) <= pivot && leftPos <= end && rightPos > leftPos) { leftPos++; // start left look for element greater than the pivot } while (array.get(rightPos) > pivot && rightPos >= start && rightPos >= leftPos) { rightPos--; // from right look for element not greater than the pivot } if (rightPos > leftPos) { swap(array, leftPos, rightPos); // if the left index is still smaller than the right index, swap the corresponding elements } } // after the indices have crossed, swap the last element in the left partition with the pivot swap(array, start, rightPos); // quicksort the left partition quickSort(array, start, rightPos - 1); // quicksort the right partition quickSort(array, rightPos + 1, end); }

The PHP implementation uses a straight integer array.

public function quickSort(&$array, $start, $end) { // Align the left and right starting positions $leftPos = $start; $rightPos = $end; // if there is only one element in the partition, do not do any sorting if (($end - $start) < 1) { return; } $pivot = $array[$start]; // keep scanning because the left and right indecies have not met while ($rightPos > $leftPos) { while ($array[$leftPos] <= $pivot && $leftPos <= $end && $rightPos > $leftPos) { $leftPos++; // start left look for element greater than the pivot } while ($array[$rightPos] > $pivot && $rightPos >= $start && $rightPos >= $leftPos) { $rightPos--; // from right look for element not greater than the pivot } if ($rightPos > $leftPos) { $this->swap($array, $leftPos, $rightPos); // if the left index is still smaller than the right index, swap the corresponding elements } } // after the indices have crossed, swap the last element in the left partition with the pivot $this->swap($array, $start, $rightPos); // quicksort the left partition $this->quickSort($array, $start, $rightPos - 1); // quicksort the right partition $this->quickSort($array, $rightPos + 1, $end); }

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:**

[visualizer id=”472″]

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.

xdebug.max_nesting_level=200

**Tech Specs**

Java JDK 8 / 7

PHP 5.5 (2GB memory allocated)

AMD FX 8-core

16gb RAM 1600mhz