In PHP How Does Usort() Function Works

In php how does usort() function works

The function cmp itself doesn't do the sorting. It just tells usort if a value is smaller, equal or greater than another value. E.g. if $a = 5 and $b = 9 it will return 1 to indicate that the value in $b is greater than the one in $a.

Sorting is done by usort.

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]

usort and compare function with arguments PHP

When you call the compare($x, $y) function, you are passing the strings as the parameters. These string are treated as arrays with 0-based indexing.

So, when echo compare('Tires', 'Tires' ); is executed, these two strings are passed and according to compare function, the character at index 1(indexing starts at 0) i.e. 2nd character is compared.

So, for this ```echo compare('Tires', 'Tires' );```, the compared characters are 'i' and 'i' which are equal and hence 0 is returned.

So, for this echo compare('Oil', 'Spark Plugs' );, the compared characters are 'i' and 'p'. 'i' is less than p and hence -1 is returned. To decide which character is lower than the other, lookup ASCII codes.

And so on for other function calls. Let me know, if you still have any doubt.

This I have explained for just the independent echo compare('Oil', 'Spark Plugs' ); line not for usort function.

UPDATE For the usort function
Let me first explain the way a comparator functions works. Whenever two parameters are passed to the compare function, it returns true or false and this is used to determine whether you need to swap those values or not.

In the earlier case, echo compare('Tirez', 'Tires' );

$x = Tires, and

$y = Tirez
You compare $x[1] and $y[1], particularly the character at index 1. But what if in the case of these strings, you just do $x < &y, the strings are compared automatically character-by-character according to ASCII codes for English alphabets and the result is returned on the first position, the characters do not match.

i.e. if you want to compare if one string is lexicographically smaller than the other string then you can use the below comparator function.

function compare($x, $y) {
    if ($x == $y) {
        return 0;
    } else if ($x < $y) {
        return -1;
    } else {
        return 1;
    }
}

The output will be 1, since while comparing character-by-character 'z' > 's'.

So, when a complete array is passed to compare function, the first two elements are passed. Here the array $products is a 2D array (an array of arrays), so the first two arrays are passed

i.e. $x = array('TIR', 'Tires', 100), and

$y = array('OIL', 'Oil', 10)
So, it depends on your requirement. For example, if you want to sort by index 0 of any array of $products i.e. 'TIR', 'OIL', 'SPK' then change the comparator function to $x[0] and $y[0].

I hope you are able to understand now :).

PHP Sorting Array Using usort() Not Working

If you are sorting string values, you should use strcmp

usort($dc_array_process, function($a, $b) {
    return strcmp($a['robo'], $b['robo']);
});

usort($dc_array_process, function($a, $b) {
    return -strcmp($a['robo'], $b['robo']);  //negative to reverse
});

document:

int strcmp ( string $str1 , string $str2 )

Returns < 0 if str1 is less than str2; > 0 if str1 is greater than
str2, and 0 if they are equal.

usort within a custom function in php

$key doesn't exist in the context of your anonymous function so pass it using use.

usort($arr, function($a, $b) use ($key) {
    return strcmp($a[$key], $b[$key]);
});

http://php.net/manual/en/functions.anonymous.php

How to view the steps of the usort() in PHP?

Using some debug output in your comparison function you can only see the comparisons that PHP does, but can't see intermediate states of the array.

But the algorithm used in usort is well known - it's QuickSort ( Which sort algorithms does PHP's usort apply? ).

You can see its vizualisation at http://www.algomation.com/algorithm/quick-sort-visualization (or just google "quicksort algorithm visualization")

PHP usort function returning incorrect results when sorting nested arrays

Altered @myxaxa's answer to use simple logic instead of funky math.

$order = array(1, 0);

usort($sort_arr, function($a, $b) use ($order){
    foreach($order as $col){
        $res = strnatcmp($b[$col], $a[$col]);
        // if the current values are not equal, return
        if( $res !== 0 ) {
            return $res;
        }
        // otherwise keep going
    }
    // if everything's equal we fall out of the loop here and return the last comparison
    return $res;
});

PHP usort() for Dummies

$a and $b are the two values being compared in the custom comparison function.

If you have array( 3, 2, 5, 6, 1) that you're sorting, you'll find cmp() compares 3 to 2, 2 to 5, 5 to 6, etc. until the values are properly sorted.

So, for example:

<?php

function cmp($a, $b)
{
    echo "$a :compared with: $b <br/>";
    if ($a == $b) {
        return 0;
    }
    return ($a < $b) ? -1 : 1;
}

$arr = array(3, 2, 5, 6, 1);

usort($arr, "cmp");

outputs:

5 :compared with: 2
5 :compared with: 3
5 :compared with: 6
1 :compared with: 5
2 :compared with: 1
3 :compared with: 2

I see usort() usually used to make much more intricate comparisons, where you need to break apart the value and compare just a piece of it, or assign custom priorities (e.g. sort by title President, Vice President, Secretary, etc., by priority and not by alphanumeric value)

In PHP How Does Usort() Function Works