How does callback sort functions work internally?

Question

In php, when we want to order a array in a customised way we can use the function usort.

I know that for this function to work, we must use values 1, 0 and -1.

In case, if I wanted to order this array down in descending order, we could do so:

$array[0]['preco'] = 10.00;
$array[1]['preco'] = 25.00;
$array[2]['preco'] = 20.00;


usort($array, function ($a, $b)
{ 
     return $b['preco'] > $a['preco'] ? 1 : 0;
});

The result would be:

[
     [
       "preco" => 25.0,
     ],
     [
       "preco" => 20.0,
     ],
     [
       "preco" => 10.0,
     ],
   ]
]

If I reversed the variables in the comparison, the result would be different:

  usort($array, function ($a, $b) {
        $a['preco'] > $b['preco'] ? 1 : 0;
  });

The result would be:

[
     [
       "preco" => 10.0,
     ],
     [
       "preco" => 20.0,
     ],
     [
       "preco" => 25.0,
     ],
   ]

I also usually reduce the comparison by simply doing a subtraction operation, when I want to order backwards:

   usort($array, function ($a, $b)
   {
       return $b['preco'] - $a['preco'];
   });

I know that if we used the value 0 for all comparisons, the results would remain in the same position.

I know how to change the ordering of values, but I don’t understand how php does it internally.

And it is possible to do this operation in Python also.

Example:

lista = [1, 2, 3]

lista.sort(lambda a,b: b-a)

#[3, 2, 1]

How is this comparison made, so that the languages knew which is the first and which is the second?

What represents the 1 or the -1, internally, for these ordination functions?

Answer 1

The programmer does not have access to the algorithm that the language uses to sort, and this probably depends on the implementation.

But whatever the sort algorithm, it works by comparing pairs of elements of the set to be ordered (I don’t say all work like this, but at least the best known). This is why callback takes two arguments (a pair of elements) and returns how they compare to each other, being:

• -1 (or other negative) if a is less than b (i and.., a should stay before b).
• 0 if the items are equal or equivalent.
• 1 (or other positive) if b is less than a (i and.., b should stay before a).

Callback gives you the opportunity to sort by the criteria you want: by an object property, by a composition of values, by anything. You decide what comes first in each pair. The language takes this information and puts the set in the order you decided, using a certain algorithm that it implements internally.

I won’t go into detail about the workings of the best known sorting algorithms (each deserves a question), but the illustrations below clearly show how they operate by comparing pairs of elements. Note the red indications.

Bubble Sort

Merge Sort

Heap Sort

Quick Sort