It is based on the smilie_id in the xf_smilie table, which itself is based on the order the smilies are added.What determines the sort order of smileys in Redactor? It seems random. Really need to be able to organise these so the smiley drop down is tidied up.
If you want to re-order them, you can simply edit the smilie_id and then edit and save one of the smilies in the ACP to update them.