Benchmark 14 sorting algorithms on arrays with different dimensions and content

This article focuses on the sorting benchmark written in PHP.

A total of 14 algorithms are presented:

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

')


The algorithms are not arranged in alphabetical order, but in order of decreasing their speed when sorting an array of 8 thousand elements.

The dimensions of the arrays used for sorting are:

• one
• 100
• 200
• 400
• 600
• 800
• 1000
• 5000
• 10,000
• 15,000
• 20,000
• 25,000
• 30,000

Also, each measurement was made with a different array filling, transmitted to the sort function:

• In the first case, the array was filled with random values ​​from the interval (1, n), where n is the dimension of the array.
• In the second case, the array was filled with random values ​​from the interval (1, PHP_INT_MAX), where PHP_INT_MAX is the maximum value of an INT type variable in the current system. On my system, this value is 2 ⁶³ , that is, around 9.2233720368548E + 18

Each measurement was made three times and the arithmetic average was taken.

Arrays up to thousands of elements

All sorting functions are included in this category.

Arrays of up to 30 thousand elements

This time, the 5 fastest algorithms are involved: sorting by counting, quick sorting, sorting by comb, sorting by heap and sorting by merge.

Arrays of up to 200 thousand elements

This time all the same 5 algorithms are involved: sorting by counting, quick sorting, sorting by comb, sorting by heap and sorting by merge.

Arrays of up to 2,000,000 items

Two algorithms took part in the last run for 2 million elements: sorting by counting and quick sorting.

findings

QuickSort is considered to be a good enough algorithm. CountingSort is very good at small ranges of values, otherwise it does not cope due to lack of memory. Shaker sorting turned out to be a bad choice for random values. "Bubble" and its modifications are not applicable for practical use.

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