Add `Array.sort_stable` and `Array.sort_custom_stable`

[aaronp64]

Implemented stable sorting for Arrays using merge sort/insertion sort

Closes https://github.com/godotengine/godot-proposals/issues/5552

Questions

• Is replacing the existing methods with stable versions an option, or should these be kept separate?
• How to add documentation for new methods - just add to the xml file, or is there anywhere else that needs to be updated?
• How to make new methods available for C#?

Performance comparisons

In general, _stable sort functions are usually faster than existing sort functions, more so when comparison is expensive, which mainly happens with custom sorts that call into gdscript. Larger arrays of expensive to copy objects may be slower with _stable functions.

Compared with gdscript below. Note that shuffling/reversing the array before each sort is included in the timing

func _ready():
	run_test("sort_small")
	run_test("sort_small_stable")
	print("-".repeat(30))
	run_test("sort_mid")
	run_test("sort_mid_stable")
	print("-".repeat(30))
	run_test("sort_large")
	run_test("sort_large_stable")
	print("-".repeat(30))
	run_test("sort_mid_str")
	run_test("sort_mid_str_stable")
	print("-".repeat(30))
	run_test("sort_large_str")
	run_test("sort_large_str_stable")
	print("-".repeat(30))
	run_test("sort_custom")
	run_test("sort_custom_stable")
	print("-".repeat(30))
	run_test("sort_reversed")
	run_test("sort_reversed_stable")

func sort_small():        run_sort(range(5), 500000, func(a): a.shuffle(), func(a): a.sort())
func sort_small_stable(): run_sort(range(5), 500000, func(a): a.shuffle(), func(a): a.sort_stable())

func sort_mid():        run_sort(range(1000), 1000, func(a): a.shuffle(), func(a): a.sort())
func sort_mid_stable(): run_sort(range(1000), 1000, func(a): a.shuffle(), func(a): a.sort_stable())

func sort_large():        run_sort(range(1000000), 1, func(a): a.shuffle(), func(a): a.sort())
func sort_large_stable(): run_sort(range(1000000), 1, func(a): a.shuffle(), func(a): a.sort_stable())

func sort_mid_str():        run_sort(range(1000).map(str), 1000, func(a): a.shuffle(), func(a): a.sort())
func sort_mid_str_stable(): run_sort(range(1000).map(str), 1000, func(a): a.shuffle(), func(a): a.sort_stable())

func sort_large_str():        run_sort(range(1000000).map(str), 1, func(a): a.shuffle(), func(a): a.sort())
func sort_large_str_stable(): run_sort(range(1000000).map(str), 1, func(a): a.shuffle(), func(a): a.sort_stable())

func sort_custom():
	run_sort(range(1000), 1000, func(a): a.shuffle(), func(a): a.sort_custom(func(a1, a2): return a1 > a2))
func sort_custom_stable():
	run_sort(range(1000), 1000, func(a): a.shuffle(), func(a): a.sort_custom_stable(func(a1, a2): return a1 > a2))

func sort_reversed():        run_sort(range(100000), 10, func(a): a.reverse(), func(a): a.sort())
func sort_reversed_stable(): run_sort(range(100000), 10, func(a): a.reverse(), func(a): a.sort_stable())

func run_sort(arr : Array, loop_count : int, reset_func : Callable, sort_func : Callable):
	for i in loop_count:
		reset_func.call(arr)
		sort_func.call(arr)

func run_test(test_name : String):
	var start := Time.get_ticks_msec()
	call(test_name)
	var end := Time.get_ticks_msec()
	print("%s: %dms" % [test_name.rpad(21), end - start])

Results:

sort_small           : 355ms
sort_small_stable    : 346ms
------------------------------
sort_mid             : 256ms
sort_mid_stable      : 260ms
------------------------------
sort_large           : 534ms
sort_large_stable    : 463ms
------------------------------
sort_mid_str         : 494ms
sort_mid_str_stable  : 454ms
------------------------------
sort_large_str       : 1616ms
sort_large_str_stable: 1755ms
------------------------------
sort_custom          : 1470ms
sort_custom_stable   : 1109ms
------------------------------
sort_reversed        : 228ms
sort_reversed_stable : 197ms

Todo:

• [x] Add tests
• [x] Update docs
• [ ] Add for C#