What Sort Algorithm Does PHP Use

What sort algorithm does PHP use?

You could find the information by looking at the php manual. http://php.net/sort says PHP uses an implementation of Quicksort. Failing that, you could always trudge through the PHP source code itself.

Is this algorithm faster then php sort()?

As pointed out in What sort algorithm does PHP use?, the built-in sorting algorithm is Quicksort. The average performance of Quicksort is O(n log n).

Your algorithm is similar to Bubble Sort. Its average performance is O(n²). But since your code goes back to the beginning after each swap, which is unnecessary, it's even worse than bubble sort.

For large arrays, Quicksort will be significantly faster than Bubble Sort.

Also, the sort() function is implemented in C code, which is compiled to machine code. Using a sorting algorithm written in PHP will have additional overhead of the PHP interpreter.

You also have a number of unnecesary arrays $i and $z, which should just be ordinary variables.

$a = array(0,3,4,2,7,6,6,8,6,1);
$z = count($a)-1;
for($i = 0;$i < $z; $i++){
    if($a[$i] > $a[$i+1]){
        $temp = $a[$i];
        $a[$i] = $a[$i+1];
        $a[$i+1] = $temp;
        $i = -1;
    }   
}

How the usort() sorting algorithm works?

How does the comparator work?

I'm not sure wether this was part of the question, but to be clear about how the comparator works:
You have an order specified by ordered list $order and a special comparator callback list_cmp which (should) return wether argument

$a is smaller than $b (return -1 or a value < 0)
$a greater than $b (return 1 or a value > 0)
$a equal $b (return 0)

list_cmp does this by looking up its order table and rather checking if

$a has a smaller (or equal) order in which case the loop exits early with return 0 or if
$b has a smaller order in which case the loop exits early with return 1.

Be aware that this is wrong according to the PHP Documentation which states it wants positive/negative/0 as return values. This is only correct if you know that the internals only check for comparator($a,$b) > 0, meaning it only checks if $b is smaller than and not equal to $a, making this a comparison order of $a <= order of $b. It can easily break if the code starts to check for $a being smaller than and not equal to $b.

How does the ~~quicksort~~ sorting work?

For starters I'm assuming you are using PHP 7 or higher. In that case you hit a special case with 6-15 Element sized arrays. PHP 7+ does not seem to use quicksort for short lists, instead it uses an Insertion Sort Variant (which is most probably faster due to Hardware related stuff like caching/code locality). You can check the sorting source code f.e. on the Github PHP Mirror (as an example: PHP 7.0 Zend/Zend_sort.c Line 177-198).

The code works in 3 steps:

comparision: compare neighbor elements array[j] and array[j+1], if array[j] <= array[j+1] move on, else goto 2.
find insertion point: now if array[j] > array[j+1], scan backwards to find the point where array[x] < array[j+1] <= array[x+1] for x < j (obviously only until x hits the start)
insert: shift elements x+1 ... j one up such that it becomes x+2 ... j+1 and insert former element at position x+1

If you apply that code to the pairings (2-1, 2-3, 1-3, 2-4, 3-4, 2-2, 2-1, 2-1, 4-1, 3-1, 1-1, 2-2) it gets obvious what the code does.

-- [2,1],3,4,2,1,2 -> 1./2./3. compare [2,1], find and insert 1 before 2
-- 1,[2,3],4,2,1,2 -> 1./2. compare [2,3], find insert point for 3 (since order of 3 < order of 2)
-- [1,3],2,4,2,1,2 -> 3. compare [1,3], found insert point for 3 before 2
-- 1,3,[2,4],2,1,2 -> 1./2. compare [2,4], find insert point for 4 (since order of 4 < order of 2) 
-- 1,[3,4],2,2,1,2 -> 3. compare [3,4], found insert point for 4 before 2
-- 1,3,4,[2,2],1,2 -> 1. compare [2,2], skip
-- 1,3,4,2,[2,1],2 -> 1./2. compare [2,1], find insert point for 1
-- 1,3,4,[2,1],2,2 -> 2. compare [2,1], find insert point for 1
-- 1,3,[4,1],2,2,2 -> 2. compare [4,1], find insert point for 1
-- 1,[3,1],4,2,2,2 -> 2. compare [3,1], find insert point for 1
-- [1,1],3,4,2,2,2 -> 3. compare [1,1], fond insert point for 1 before 3
-- 1,1,3,4,2,[2,2] -> 1. compare [2,2], skip
-- sorted: 1,1,3,4,2,2,2

PS:
Here you already see that it is quite complex to derive the work of even a simple sorting algorithm (22 lines of code) by its comparison patterns. The PHP 7 quicksort implementation is around 10 times as big in lines of code and has some freaky optimizations (besides normal madness due to pivot selection and recursions).

Most of the times it is better to ignore in depth implementation details and only reduce it to the stuff that is needed. Typical questions for a sorting algorithm would be if it is stable/unstable and performing in O(log n) with O(n) Memory consumption. There are easier ways to learn the core algorithms behind those optimized implementations like the Quicksort Dance or any other visualization or a good old (e)book or webpage with examples.

-- Edited

Added a (bad, unoptimized, unsafe) php implementation for insertion sort for another visualization of how it works:

<?php

function my_usort($A, $comparator) {
  // Start .. End Positions
  $current_pos = 0;
  $last_pos = count($A)-1;
  // Outer Loop: each step checks that A[0] up to A[current_pos] is sorted. 
  // When the algorithm finishes we know that A[0] ... A[last_pos] is sorted
  while($current_pos < $last_pos) {
    echo "Sorted Subarray from \$A is " . json_encode(array_slice($A, 0, $current_pos+1)) . "<br>\n";
    echo "\$A looks like this now: " . json_encode($A) . 
    ", comparing [" . $A[$current_pos] . "," . $A[$current_pos +1] . "] (verify step)<br>\n";
    // "Verification Step"
    // At this point A[0] ... A[current_pos] is sorted.
    // Check A[current_pos] <= A[current_pos +1]
    if($comparator($A[$current_pos], $A[$current_pos +1]) > 0) {
      // nope, A[current_pos] > A[current_pos +1] (list_cmp/comparator returns value > 0)
      // "Insertion Step" start, find the correct position for A[current_pos+1] in the already
      // sorted list A[0] ... A[current_pos]
      $insert_point = $current_pos;
      // Swap the missmatching Neighbor pair
      echo "swapping: \$A[" . $insert_point . "] and \$A[" . ($insert_point+1) . "]<br>\n";
      $tmp = $A[$insert_point +1];
      $A[$insert_point +1] = $A[$insert_point];
      $A[$insert_point] = $tmp;
      $sorted_up_to_current_pos = false;
      // Inner Loop: find correct insertion point
      while($insert_point > 0 && !$sorted_up_to_current_pos) {
        echo "\$A looks like this now: " . json_encode($A) . 
        ", comparing [" . $A[$insert_point-1] . "," . $A[$insert_point] . "] (insertion step)<br>\n";
      // "Insertion Step", Swap the missmatching Neighbor pairs until A[0] ... A[current_pos] is sorted again
      if($comparator($A[$insert_point-1], $A[$insert_point]) > 0) {
          // Swap the missmatching Neighbor pair
          echo "swapping: \$A[" . ($insert_point-1) . "] and \$A[" . $insert_point . "]<br>\n";
          $tmp = $A[$insert_point];
          $A[$insert_point] = $A[$insert_point-1];
          $A[$insert_point-1] = $tmp;
          // goto new pair
          $insert_point = $insert_point -1;
        } else {
          // found correct spot, done
          $sorted_up_to_current_pos = true;
        }
      }
      $A[$insert_point] = $tmp;
      echo "\$A looks like this now: " . json_encode($A) . ", insertion done<br>\n";
    }
    $current_pos = $current_pos + 1;
  }
  echo "Sorted Array \$A is " . json_encode(array_slice($A, 0, $current_pos+1)) . "<br>\n";
}

function list_cmp($a, $b) {
  global $order;
  //echo "\$a=$a, \$b=$b </br>\n";

  foreach ($order as $key => $value) {
      //echo "\$value=$value </br>\n";
      if ($a == $value) {
          echo "\$a=\$value, returing 0. </br>\n";
          return 0;
      }
      if ($b == $value) {
          echo "\$b=\$value, returing 1. </br>\n";
          return 1;
      }
  }
}

$order[0] = 1;
$order[1] = 3;
$order[2] = 4;
$order[3] = 2;

$array[0] = 2;
$array[1] = 1;
$array[2] = 3;
$array[3] = 4;
$array[4] = 2;
$array[5] = 1;
$array[6] = 2;

my_usort($array, "list_cmp");

Output is complete now with currently sorted array, positions:

Sorted Subarray from $A is [2] 
$A looks like this now: [2,1,3,4,2,1,2], comparing [2,1] (verify step) 
$b=$value, returing 1.  
swapping: $A[0] and $A[1] 
$A looks like this now: [1,2,3,4,2,1,2], insertion done 
Sorted Subarray from $A is [1,2] 
$A looks like this now: [1,2,3,4,2,1,2], comparing [2,3] (verify step) 
$b=$value, returing 1.  
swapping: $A[1] and $A[2] 
$A looks like this now: [1,3,2,4,2,1,2], comparing [1,3] (insertion step) 
$a=$value, returing 0.  
$A looks like this now: [1,3,2,4,2,1,2], insertion done 
Sorted Subarray from $A is [1,3,2] 
$A looks like this now: [1,3,2,4,2,1,2], comparing [2,4] (verify step) 
$b=$value, returing 1.  
swapping: $A[2] and $A[3] 
$A looks like this now: [1,3,4,2,2,1,2], comparing [3,4] (insertion step) 
$a=$value, returing 0.  
$A looks like this now: [1,3,4,2,2,1,2], insertion done 
Sorted Subarray from $A is [1,3,4,2] 
$A looks like this now: [1,3,4,2,2,1,2], comparing [2,2] (verify step) 
$a=$value, returing 0.  
Sorted Subarray from $A is [1,3,4,2,2] 
$A looks like this now: [1,3,4,2,2,1,2], comparing [2,1] (verify step) 
$b=$value, returing 1.  
swapping: $A[4] and $A[5] 
$A looks like this now: [1,3,4,2,1,2,2], comparing [2,1] (insertion step) 
$b=$value, returing 1.  
swapping: $A[3] and $A[4] 
$A looks like this now: [1,3,4,1,2,2,2], comparing [4,1] (insertion step) 
$b=$value, returing 1.  
swapping: $A[2] and $A[3] 
$A looks like this now: [1,3,1,4,2,2,2], comparing [3,1] (insertion step) 
$b=$value, returing 1.  
swapping: $A[1] and $A[2] 
$A looks like this now: [1,1,3,4,2,2,2], comparing [1,1] (insertion step) 
$a=$value, returing 0.  
$A looks like this now: [1,1,3,4,2,2,2], insertion done 
Sorted Subarray from $A is [1,1,3,4,2,2] 
$A looks like this now: [1,1,3,4,2,2,2], comparing [2,2] (verify step) 
$a=$value, returing 0.  
Sorted Array $A is [1,1,3,4,2,2,2]

What algorithm does arsort use?

Like all PHP sort functions, the quicksort algorithm is used

See the Note in the manual:

Note: Like most PHP sorting functions, sort() uses an implementation of » Quicksort.

Which sort algorithms does PHP's usort apply?

At php.net/sort I found this:

Note: Like most PHP sorting functions, sort() uses an implementation of » Quicksort.

~~I believe that it uses a randomized quicksort, so there is no need for shuffling the array.~~

I did some tests and PHP's quicksort is not randomized, so shuffle your input array!!

How sorting works in PHP? What algorithm is used?

Use flags to change the case sensitivity of the asort() function.

$array = ["test", "Travel", "en"];
asort($array, SORT_FLAG_CASE | SORT_NATURAL);
var_dump($array);

These are documented with the sort() function.

Bubble sort implementation in PHP?

Using bubble sort is a very bad idea. It has complexity of O(n^2).

You should use php usort, which is actually a merge sort implementation and guaranteed O(n*log(n)) complexity.

A sample code from the PHP Manual -

function cmp( $a, $b ) { 
  if(  $a->weight ==  $b->weight ){ return 0 ; } 
  return ($a->weight < $b->weight) ? -1 : 1;
} 

usort($unsortedObjectArray,'cmp');

Quick Sort in PHP

Arrays are not passed by reference by default in PHP. (They're not simply pointers like they would be in C.) So your functions aren't actually changing the input array.

I've modified your function declarations below and it now works as expected.

Also, you need $pivot=$a[lower] to be $pivot=$a[$lower];;

<?php
$array=array(7, 6, 5, 9, 2, 1, 15, 7);
$L=0;
$U=count($array)-1;
function Partition(&$a, $lower, $Upper)
{   
        $i=$lower;
        $j=$Upper;
        $pivot=$a[$lower];

        while($i<$j)
        {

        while($a[$i]<$pivot)
        {
            $i++;
        }

        while($a[$j]>$pivot)
        {
            $j--;
        }

        if($i<$j)
        {
            $temp = $a[$i];
            $a[$i] = $a[$j];
            $a[$j] = $temp;
        }
        $i++;
        }
        $a[$lower]=$a[$j];
        $a[$j]=$pivot;

        return $j;
}
function QuickSort(&$a, $lower, $Upper)
{
    if($lower<$Upper)
    {
        $loc= Partition($a, $lower, $Upper);
        QuickSort($a, $lower, $loc-1);
        QuickSort($a, $loc+1, $Upper);
    }
    print_r($a);
}
QuickSort($array, $L, $U);
print_r($array);

It's worth noting that the sort functions for arrays that PHP provides already use an implementation of QuickSort.

How can sort an array without using sort() function in php?

Implementing QuickSort in PHP

Quicksort recursive.php

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));
}

Usage :

$arr = array(80, 90, 100, 10, 50, 3);

$arr = quicksort($arr);

print_r($arr);

Natural sorting algorithm in PHP with support for Unicode?

Nailed it!

$array = array('Ägile', 'Ãgile', 'Test', 'カタカナ', 'かたかな', 'Ágile', 'Àgile', 'Âgile', 'Agile');

function Sortify($string)
{
    return preg_replace('~&([a-z]{1,2})(acute|cedil|circ|grave|lig|orn|ring|slash|tilde|uml);~i', '$1' . chr(255) . '$2', htmlentities($string, ENT_QUOTES, 'UTF-8'));
}

array_multisort(array_map('Sortify', $array), $array);

Output:

Array
(
    [0] => Agile
    [1] => Ágile
    [2] => Âgile
    [3] => Àgile
    [4] => Ãgile
    [5] => Ägile
    [6] => Test
    [7] => かたかな
    [8] => カタカナ
)

Even better:

if (extension_loaded('intl') === true)
{
    collator_asort(collator_create('root'), $array);
}

Thanks to @tchrist!

What Sort Algorithm Does PHP Use