Benchmarks: 14 Sorting Algorithms and PHP Arrays

PHP

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

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.

Comments

  1. Very nice! Check out the visualization of sorting algorithms: http://sorting.at
  2. Yes, I saw that, looks amazing. It seems they only have two algorithms though.
  3. Thank you. I used your given data to create a line chart of basic Algorithms benchmark.
  4. Fastest is list merging. mlich.zam.slu.cz/js-sort/sorting2.htm Try 7 fastest algorithm and array of 1.000.000 integers, Firefox browser; 0.3s javascript. Warning: FF do code optimalization for repeating, you myabe must do refresh for more testing)

    Example1 O(n) = n to n*log(n) 4352 sorted 4, 35, 2 (multi value list) concat 345, 2 concat 2345 Example 1 you can modify for detect all sorted by ASC or DESC, as Timsort.

    Example2 O(n) = n*log(n) 4352 sorted 4, 3, 5, 2 (single list) concat 34, 25 concat 2345

1,128

Ropes — Fast Strings

Most of us work with strings one way or another. There’s no way to avoid them — when writing code, you’re doomed to concatinate strings every day, split them into parts and access certain characters by index. We are used to the fact that strings are fixed-length arrays of characters, which leads to certain limitations when working with them. For instance, we cannot quickly concatenate two strings. To do this, we will at first need to allocate the required amount of memory, and then copy there the data from the concatenated strings.