Implementing QuickSort in PHP

Quicksort is practically the fastest way to sort an array of data. PHP’s array sorting function sort() uses QuickSort.

How Quick Sort works?

This is how QuickSort operates on a list of elements:

  1. Picks a data element (called pivot) from an array;
  2. Makes a comparison of all other elements with the pivot;
  3. Creates two subsets, one with values smaller than the pivot and the other with larger values;
  4. Repeats the above steps recursively on all the subsets until all subsets are broken down to individual elements;
  5. Groups together all subsets to produce sorted array of data.

Although you have a function sort() in PHP that can do array sorting by implementing QuickSort, yet the below function from WikiBooks can be helpful in understanding the process.

function quicksort( $array ) {
    if( count( $array ) < 2 ) { return $array; } $left = $right = array( ); reset( $array ); $pivot_key = key( $array ); $pivot = array_shift( $array ); foreach( $array as $k => $v ) {
        if( $v < $pivot ) $left[$k] = $v; else $right[$k] = $v; } return array_merge(quicksort($left), array($pivot_key => $pivot), quicksort($right));
}

//Using quicksort()
$array  = quicksort( $array );    //returns sorted array.

To do quicksort with the builtin sort() function:

sort( $array );    //returns true on success, false otherwise