Benchmark of sorting algorithms written in PHP

Here is benchmark of all array sorting algorithms post in the blog. Sorting arrays of 10 000 elements:

Name	random	sorted	rsorted
straightInsertion	7.48131	0.0095	13.68925
binaryInsertion	5.46446	0.05528	10.8473
straightSelection	21.2452	21.34226	25.2773
bubbleSort	22.76245	12.45991	31.98982
shakerSort	18.75352	0.00392	32.69624
heapSort	0.11843	0.12559	0.11432
quickSortRecursive	11.91182	6.7423	6.43074
quickSortRecursiveNew	7.41534	7.45058	7.38413
quickSort	0.05555	0.02845	0.03096
sort	0.00869	0.00467	0.005

Different sort algorithms have advantage in certain conditions. So this benchmark can't show the advantage of all of them.

Function quickSortRecursive receives an array as parameter and then creates new static array for the recursion calls. quickSortRecursiveNew uses global array and it sorts random array faster then quickSortRecursive.
The iterative version of quick sort is more then 100 faster then recursive one!!!

The last function is PHP native function for sorting arrays. It so fast because it isn't run through PHP interpreter. Use PHP native functions, they are a lot faster.

The source of benchmark and all of the functions can be found here.

PHP Quicksort

Quicksort is a well-known sorting algorithm developed by C. A. R. Hoare that, on average, makes Θ(nlogn) (big O notation) comparisons to sort n items. However, in the worst case, it makes Θ(n2) comparisons. Typically, quicksort is significantly faster in practice than other Θ(nlogn) algorithms, because its inner loop can be efficiently implemented on most architectures, and in most real-world data it is possible to make design choices which minimize the possibility of requiring quadratic time.

Quicksort is a comparison sort and, in efficient implementations, is not a stable sort.


PHP implementation:

// Recursive version:
function quickSortRecursive( $arr, $left = 0 , $right = NULL )
{
 // when the call is recursive we need to change 
 //the array passed to the function yearlier
 static $array = array(); 
 if( $right == NULL )
  $array = $arr;

 if( $right == NULL )
  $right = count($array)-1;//last element of the array
 
 $i = $left;
 $j = $right;
 
 $tmp = $array[(int)( ($left+$right)/2 )];

 // partion the array in two parts. 
 // left from $tmp are with smaller values,
 // right from $tmp are with bigger ones
 do
 {
  while( $array[$i] < $tmp )
   $i++;
  
  while( $tmp < $array[$j] ) 
   $j--;
  
  // swap elements from the two sides 
  if( $i <= $j )
  {
   $w = $array[$i];
   $array[$i] = $array[$j];
   $array[$j] = $w;
   
   $i++;
   $j--;
  }
 }while( $i <= $j );
 
 // devide left side if it is longer the 1 element
 if( $left < $j )
  quickSortRecursive(NULL, $left, $j);
 
 // the same with the right side
 if( $i < $right )
  quickSortRecursive(NULL, $i, $right);

 // when all partitions have one element
 // the array is sorted
 
 return $array;
}



// Non recursive version:
function quickSort( $array )
{
 $cur = 1;
 $stack[1]['l'] = 0;
 $stack[1]['r'] = count($array)-1;
 
 do 
 {
  $l = $stack[$cur]['l'];
  $r = $stack[$cur]['r'];
  $cur--;
  
  do
  {
   $i = $l;
   $j = $r;
   $tmp = $array[(int)( ($l+$r)/2 )];

   // partion the array in two parts.
   // left from $tmp are with smaller values,
   // right from $tmp are with bigger ones
   do
   {
    while( $array[$i] < $tmp )
     $i++;
    
    while( $tmp < $array[$j] ) 
     $j--;
    
    // swap elements from the two sides 
    if( $i <= $j )
    {
     $w = $array[$i];
     $array[$i] = $array[$j];
     $array[$j] = $w;
     
     $i++;
     $j--;
    }
   
   }while( $i <= $j );
   

   if( $i < $r )
   {
    $cur++;
    $stack[$cur]['l'] = $i;
    $stack[$cur]['r'] = $r;
   }
   $r = $j;
  
  }while( $l < $r );
  
 }while( $cur != 0 );

 return $array;
}

PHP Heapsort

Heapsort is a comparison-based sorting algorithm, and is part of the selection sort family. Although somewhat slower in practice on most machines than a good implementation of quicksort, it has the advantage of a worst-case O(n log n) runtime. Heapsort is an in-place algorithm, but is not a stable sort.

During extraction, the only space required is that needed to store the heap. In order to achieve constant space overhead, the heap is stored in the part of the input array that has not yet been sorted. (The structure of this heap is described at Binary heap: Heap implementation.)

Heapsort uses two heap operations: insertion and root deletion. Each extraction places an element in the last empty location of the array. The remaining prefix of the array stores the unsorted elements.


PHP implementation:

function heapSort( $array )
{
 $right = count( $array )-1;
 $left = (int)($right/2) + 1;
 
 while( $left > 0 )
 {
  $left--;
  sift($array, $left, $right);
 }
 
 while( $right > 0 )
 {
  $tmp = $array[0];
  $array[0] = $array[$right];
  $array[$right] = $tmp;
  $right--;
  
  sift($array, $left, $right);
 }
 
 return $array;
}
function sift( &$array, $left, $right )
{
 $i = $left;
 $j = 2*$i;
 $tmp = $array[$i];
 
 while( $j <= $right )
 {
  if( $j < $right && $array[$j] < $array[$j+1] )
   $j++;
  if( $tmp >= $array[$j] ){
   $array[$i] = $tmp;
   return 0;
  }
  $array[$i] = $array[$j];
  $i = $j;
  $j = 2*$i;
 }
 
 $array[$i] = $tmp;
}

PHP Shaker Sort

Shaker sort is a simple optimization that does passes in both directions, allowing out of place items to move fast across the whole array. Same complexity as Bubble sort, only works much better when some smal items are at the end of the array.


PHP implementation:

function shakerSort( $array )
{

 $l = 1;
 $r = count($array)-1;
 $k = $r;
 
 do
 {
  //move smaller values to the left
  for( $j=$r; $j >= $l; $j-- )
   if( $array[$j-1] > $array[$j] )
   {
    $tmp = $array[$j-1];
    $array[$j-1] = $array[$j];
    $array[$j] = $tmp;
    $k = $j;
   }
  $l = $k+1;
  // move bigger values to the right
  for( $j=$l; $j <= $r; $j++ ){
   if( $array[$j-1] > $array[$j])
   {
    $tmp = $array[$j-1];
    $array[$j-1] = $array[$j];
    $array[$j] = $tmp;
    $k = $j;
   }
  }
  $r = $k-1;
 }while( $l <= $r );

 return $array;
}

PHP Bubble sort

Bubble sort is a simple sorting algorithm. It works by repeatedly stepping through the list to be sorted, comparing two items at a time and swapping them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which means the list is sorted.

example: 5 1 4 2 8 - unsorted array 1 4 2 5 8 - after one pass 1 2 4 5 8 - sorted array

The algorithm gets its name from the way smaller elements "bubble" to the top (i.e. the beginning) of the list via the swaps. (Another opinion: it gets its name from the way greater elements "bubble" to the end.) Because it only uses comparisons to operate on elements, it is a comparison sort. This is the easiest comparison sort to implement.


PHP implementation:

function bubbleSort( $array )
{
 
 for( $i=1; $i < count($array); $i++ )
  // move smaller from two elements up until reach current position
  for( $j = (count($array)-1); $j >= $i; $j-- )
   if( $array[$j-1] > $array[$j] )
   {
    $tmp = $array[$j-1];
    $array[$j-1] = $array[$j];
    $array[$j] = $tmp;
   }

 return $array;
}

PHP Selection sort

Selection sort is a sorting algorithm, specifically an in-place comparison sort. It has Θ(n2) complexity, making it inefficient on large lists, and generally performs worse than the similar insertion sort. Selection sort is noted for its simplicity, and also has performance advantages over more complicated algorithms in certain situations. It works as follows:

1. Find the minimum value in the list
2. Swap it with the value in the first position
3. Repeat the steps above for remainder of the list (starting at the second position)


Effectively, we divide the list into two parts: the sublist of items already sorted, which we build up from left to right and is found at the beginning, and the sublist of items remaining to be sorted, occupying the remainder of the array.


PHP implementation:

function straightSelection( $array )
{

 for( $i=0; $i < count($array); $i ++ )
 {
  $k = $i;
  $tmp = $array[$i];
  
  // search elements right to current for the smallest
  for( $j = $i+1; $j < count($array); $j++ )
   if( $array[$j] < $tmp )
   {
    $k=$j;
    $tmp = $array[$j];
   }
  
  // switch places of current element and previously found
  $array[$k] = $array[$i];
  $array[$i] = $tmp;
 }

 return $array;
}

PHP Binary Insertion sort

The straight insertion algorithm presented in the preceding section does a linear search to find the position in which to do the insertion. However, since the element is inserted into a sequence that is already sorted, we can use a binary search instead of a linear search. Whereas a linear search requires Θ(n) comparisons in the worst case, a binary search only requires Θ(logn) comparisons. Therefore, if the cost of a comparison is significant, the binary search may be preferred.


PHP implementation:

function binaryInsertion( $array )
{
 
 for( $i=1; $i < count($array); $i++ )
 {
  $tmp = $array[$i];
  $left = 0;
  $right = $i-1;
  
  // finds the last element with value smaller then current element
  // all elements before the current are sorted
  // so we can find the middle and
  // check only the right(correct) half
  while( $left <= $right )
  {
   $middle = (int)(($left+$right)/2);
   if( $tmp < $array[$middle] )
    $right = $middle - 1;
   else
    $left = $middle + 1;
  }
  // loop until current element is smaller than previous.
  // if so replace current with previous.
  for( $j = $i-1; $j >= $left; $j-- )
   $array[$j+1] = $array[$j];
  
  $array[$left] = $tmp;
  // now we can write current element's value on its position.
 }

 return $array;
}

PHP Straight Insertion sort

The key step of any insertion sorting algorithm involves the insertion of an item into a sorted sequence. There are two aspects to an insertion--finding the correct position in the sequence at which to insert the new element and moving all the elements over to make room for the new one.

This section presents the straight insertion sorting algorithm. Straight insertion sorting uses a linear search to locate the position at which the next element is to be inserted.


PHP implementation:

function straightInsertion( $array )
{
 
 for( $i=1; $i < count($array); $i++ )
 {
  $tmp = $array[$i];
  // store current element's value because it
  // will be overwritten if it is not in its place
  
  // loop until current element is smaller than previous.
  // if so replace current with previous.
  for( $j = $i-1; $tmp < $array[$j]; $j-- )
   $array[$j+1] = $array[$j];

  // now we can write current element's value on its position.
  $array[$j+1] = $tmp;
 }

 return $array;
}