Introduce a stable sorting method for `table`

[Nyapaw]

I've implemented a non-native stable sorting algorithm in Luau based on a merge sort algorithm very similar to C++'s std::stable_sort implementation.

I wrote:

There is no sorting algorithm implementation native to Luau that is stable, meaning that they preserve the order of non-unique elements.

Stability is important for some game mechanics such as having a shop display which might need multiple runs through the algorithm to give the most relevant results. For example, you might want to sort the price of the item in ascending order, and then the name of the item in lexicographic order. If you use a non stable-sort, you cannot sort by price of items with the same price without having shuffled the ordering of the names.

Previously, I've made a feature request on the relative worst-case inefficiency of table.sort compared to other compiler implementations in other languages, and I am glad that got addressed recently; table.sort now uses introspection to guarantee a O(n*log(n)) worst-case time complexity.

However, introspective sort, being a derivative of quicksort and heapsort, does not provide stability. I'd like to propose a new method for the table library, preferably table.stablesort(tbl, comparer).

As for the choice of algorithm, in many languages (such as Java, Python, and JavaScript) the compiler or interpreter implements Timsort, an adaptive version of merge sort. It guarantees O(n*log(n)) worst-case time complexity.

[chriscerie]

For example, you might want to sort the price of the item in ascending order, and then the name of the item in lexicographic order.

It’ll be helpful to provide a different use case where sorting with multiple passes is truly needed, because the example can be done by defining both criteria in the custom comparator.