TimSort for byond:

RESULTS:
sorting 10 random lists of length 3 to 303 in increments of 3
(Meh, I forgot to refresh this one, there were only 338 trials rather than 1010, can't be bothered to recode the test)
                                    Profile results (total time)
Proc Name                                             Self CPU    Total CPU    Real Time        Calls
-------------------------------------------------    ---------    ---------    ---------    ---------
/proc/sortList                                           0.672       16.141       16.243       171226  <--TG's current mergesort(recursive, hence the higher number of calls)
/proc/sortTim                                            0.008        3.278        3.274          338  <--TimSort
/proc/sortMerge                                          0.011        2.839        2.855          338  <--new mergesort
/proc/sortInsert                                         0.010        2.124        2.103          338  <--binary insertion

Sorting 10 presorted lists with 3 inversions (3 elements shuffled up), Lists of length 3 to 303 (increments of 3)
                                    Profile results (total time)
Proc Name                                             Self CPU    Total CPU    Real Time        Calls
-------------------------------------------------    ---------    ---------    ---------    ---------
/proc/sortList                                           1.290       23.056       23.254       308050	<--rather cataclysmic
/proc/sortMerge                                          0.015        4.077        4.068         1010	<--
/proc/sortInsert                                         2.639        3.472        3.464         1010	<--
/proc/sortTim                                            0.014        1.567        1.576         1010	<--TimSort is faaar more effective in these cases,
Timsort can exploit runs effectively

sorting 10 presorted lists which have been reversed
                                    Profile results (total time)
Proc Name                                             Self CPU    Total CPU    Real Time        Calls
-------------------------------------------------    ---------    ---------    ---------    ---------
/proc/sortList                                           1.234       23.193       23.295       308050
/proc/sortMerge                                          0.023        4.681        4.686         1010
/proc/sortInsert                                         2.875        3.750        3.765         1010
/proc/sortTim                                            0.020        3.294        3.284         1010	//This can be lower by using a different comparison method
 *Corrected: /proc/sortTim                                0.017        0.665        0.663         1010	//Using a non-strictly ascending comparison

sorting 10 presorted lists
                                    Profile results (total time)
Proc Name                                             Self CPU    Total CPU    Real Time        Calls
-------------------------------------------------    ---------    ---------    ---------    ---------
/proc/sortList                                           1.199       21.391       21.517       308050
/proc/sortMerge                                          0.018        3.724        3.729         1010
/proc/sortInsert                                         2.497        3.302        3.309         1010
/proc/sortTim                                            0.024        0.586        0.584         1010

Summary, all the new procs are faster than the old ones. TimSort is ever so slightly slower than Insertion and Merging on random lists. But on lists with natural runs (partially sorted data) it is far faster than all others.

The old merge sort was removed and replaced with timSort. Other algorithms are provided as alternatives.

All algorithms use a central datum, so accept many of the same parameters. For instance, setting associative=1 will make them sort associative lists by their associated values, rather than keys.
They also accept a cmp argument. This allows sorting of lists of datums, text, numbers or whatever. The pre-existing helpers in lists.dm were rewritten as examples.
Accidentally left some duplicate code in, which was used to keep sortInsert's calls to binarySort() separate from timSort's calls to binarySort
Merge pull request #4634 from Carn/timSort

TimSort for byond