Benchmarking 14 PHP Sorting Algorithms: Speed Rankings and Insights

In this article I introduce tests of sorting algorithms implemented in PHP.

The 14 algorithms tested are:

Quick sort

Counting sort

Comb sort

Heap sort

Merge sort

Shell sort

Selection sort

Insertion sort

Gnome sort

Comb bubble sort

Cocktail sort

Bubble sort

Odd‑even sort

Flagged bubble sort

The algorithms are ordered not alphabetically but by their overall speed when sorting 8,000 elements.

Array sizes used for testing are:

1

100

200

400

600

800

1,000

5,000

10,000

15,000

20,000

25,000

30,000

Each measurement uses a different array size passed to the sorting function.

Two data generation cases are considered: random values between 1 and N (array size) and random values between 1 and PHP_INT_MAX.

Each test is run three times and the arithmetic mean is taken.

1,000‑element array

Results for all algorithms at this size are shown below.

30,000‑element array

The five fastest algorithms (Counting, Quick, Comb, Heap, Merge) are tested.

200,000‑element array

The same five fastest algorithms are tested.

2,000,000‑element array

Only Counting sort and Quick sort are evaluated.

Conclusion: Quick sort proves to be an excellent algorithm. Counting sort performs well on small value ranges; other algorithms suffer from high memory usage. Cocktail sort is a poor choice for random data. Bubble sort and its variants are unsuitable for practical use.

All source code and results are available at: https://drive.google.com/file/d/0B63HSL7JD630VWdSSFgwdHR5RkU/edit?usp=sharing

Using built‑in sort functions is an interesting exercise, but interpreted PHP sorting functions can never match the speed of the C‑based sort() implementation.

Original author: ahwoobachairiesaas Translator: 伯乐在线 - 姚开健 Link: http://blog.jobbole.com/68774/