Benchmarks: 14 Sorting Algorithms and PHP Arrays

In this article I will tell you about the benchmark of sorting algorithms, written on PHP.
There are 14 algorithms presented:

• quickSort
• countingSort
• combSort
• heapSort
• mergeSort
• shellSort
• selectionSort
• insertSort
• gnomeSort
• combinedBubbleSort
• cocktailSort
• bubbleSort
• oddEvenSort
• bubbleSortWithFlag

Algorithms are not alphabetically ordered, but in order of their performance speed descending when sorting an array of 8 thousand elements.

The following arrays dimensions, used for sorting, are presented:

• 1
• 100
• 200
• 400
• 600
• 800
• 1000
• 5000
• 10000
• 15000
• 20000
• 25000
• 30000

Each measurement was performed with different array filling, which is passed to sorting function.

• In the first case the array has been filled by random values with a (1, n) interval, in which n — is an array dimension.
• In the second case the array has been filled by random values with a (1, PHP_INT_MAX) interval, in which PHP_INT_MAX — is maximum variable value of INT type in the current system. In my system it’s 2^63 or approx 9.2233720368548E+18

Each measurement has been performed three times and an arithmetic mean has been taken

Arrays of up to 1000 elements

All sorting functions are involved in this category.

Arrays of up to 30 thousand elements

In this case 5 the fastest algorithms are involved: counting, quick, comb, heap and merge sorts.

Arrays of up to 200 thousand elements

In this case the same 5 algorithms are involved: counting, quick, comb, heap and merge sorts.

Arrays of up to 2 million elements

In the last round of 2 million elements two algorithms were involved: count sort and quick sort.

Summary

QuickSort is rightfully considered quite a good algorithm. CountingSort is really good at small value ranges; otherwise it can’t manage due to low memory. Cocktail sort proved to be a bad choice for random values. Bubble sort and its modifications are not applicable to practical use.

Source code of all algorithms + results: https://drive.google.com/file/d/0B63HSL7JD630VWdSSFgwdHR5RkU/edit?usp=sharing

While a fun exercise, use the built in sort function. Building a sort function in interpreted PHP code will never be faster than the C variant that sort() employs.