[Discussion] Which sorting algorithm is used in the C implementation of the PHP sorting series functions?

ext/standard/php_array.h

https://github.com/php/php-src/blob/master/ext/standard/php_array.h

#ifndef PHP_ARRAY_H
#define PHP_ARRAY_H

PHP_MINIT_FUNCTION(array);
PHP_MSHUTDOWN_FUNCTION(array);

PHP_FUNCTION(ksort);
PHP_FUNCTION(krsort);
PHP_FUNCTION(natsort);
PHP_FUNCTION(natcasesort);
 PHP_FUNCTION(asort);
PHP_FUNCTION(arsort);
PHP_FUNCTION(sort);
PHP_FUNCTION(rsort);
PHP_FUNCTION(usort);
PHP_FUNCTION(uasort);
PHP_FUNCTION(uksort);
...

The sorting function defined above:

arsort -- Sort an array in reverse order while maintaining index relationships asort – Sort an array while maintaining index relationships krsort -- Sort an array in reverse order by key name ksort -- Sort an array by key natcasesort -- Sort an array in a case-insensitive manner using the "natural sort" algorithm natsort -- Sort an array using the "natural sorting" algorithm rsort -- Sort an array in reverse order sort -- Sort the array uasort – Sort values ​​in an array using a user-defined comparison function and maintain index association uksort -- Sort keys in an array using a user-defined comparison function usort – Sort values ​​in an array using a user-defined comparison function

For simplicity, only analyze the sort function: https://github.com/php/php-src/blob/master/ext/standard/array.c

{/ *{{Proto Bool Sort (Array & Array_arg [, Int Sort_flags])

 long sort_type = p Hp_sort_regular;

 if (zend_parse_parameters (ZEND_NUM_ARGS() TSRMLS_CC, "a|l", &array, &sort_type) == FAILURE) {
 RETURN_FALSE;
 }

 php_set_compare_func(sort_type TSRMLS_CC);

 if (zend_hash_sort(Z_ARRVAL_P(array), zend_q sort, php_array_data_compare, 1 TSRMLS_CC) == FAILURE) {
 RETURN_FALSE;
 }
 RETURN_TRUE;
}
/* }}} */



Copy code

High possibility of using quick sort.

Continue to analyze.

Zend/zend_hash.c

https://github.com/php/php-src/blob/master/Zend/zend_hash.c

(*sort_func)((void *) arTmp, i, sizeof(Bucket *), compar TSRMLS_CC);

 ht->pInternalPointer = ht->pListHead;

 arTmp[0]->pListLast = NULL;
 if (i > 1) {
 arTmp[0]->pListNext = arTmp [1];
 for (j = 1; j < i-1; j++) {
 arTmp[j]->pListLast = arTmp[j-1];
 arTmp[j]->pListNext = arTmp[ j+1];
 }
 arTmp[j]->pListLast = arTmp[j-1];
 arTmp[j]->pListNext = NULL;
 } else {
 arTmp[0]->pListNext = NULL;
 }
 ht->pListTail = arTmp[i-1];

 pefree(arTmp, ht->persistent);
 HANDLE_UNBLOCK_INTERRUPTIONS();

 if (renumber) {
 p = ht-> pListHead;
 i=0;
 while (p != NULL) {
 p->nKeyLength = 0;
 p->h = i++;
 p = p->pListNext;
 }
 ht-> nNextFreeElement = i;
 zend_hash_rehash(ht);
 }



Copy code

Exchange space for time

)

What kind of php was used