Stable Sort by Property Value

stable_sort_by_prop.gd

# Implements a stable sort as requested in https://www.reddit.com/r/godot/comments/1cyyaxo/are_there_any_plans_to_implement_a_stable_sorting/
# in the worst possible way

extends Node

class TestObject extends RefCounted:
	const SUITES = ['♠️','♣️','♥️','♦️']
	var an_int : int
	var a_float : float
	var a_string : String
	func _init() -> void:
		an_int = randi_range(0, 100)
		a_float = randf()
		a_string = SUITES.pick_random()
	func _to_string() -> String:
		return "(%s, %s, %s)" % [an_int, a_float, a_string]


func _ready() -> void:
	_test(10, "an_int", true)
	_test(10, "a_float", true)
	_test(10, "a_string", true)
	
	_test(100, "an_int") 
	_test(10_000, "an_int") 
	_test(100_000, "an_int") 
	_test(1_000_000, "an_int") 
	
	_test(100, "a_float")
	_test(10_000, "a_float")
	_test(100_000, "a_float")
	_test(1_000_000, "a_float")
	
	_test(100, "a_string")
	_test(10_000, "a_string")
	_test(100_000, "a_string")
	_test(1_000_000, "a_string")

func _test(amount : int, comparison_prop : StringName, print_result := false):
	var array = []
	for i in amount:
		array.append(TestObject.new())
	var start_time = Time.get_ticks_msec()
	var sorted = sort_objects_by_prop(array, comparison_prop)
	print("Prop name: %s. Amount: %s Elapsed: %sms" % [comparison_prop, amount, (Time.get_ticks_msec() - start_time)] )
	if print_result:
		print(array)
		print(sorted)


static func sort_objects_by_prop( array : Array, comparison_prop : StringName) -> Array:
	var split = {}
	# split the array in groups based on the value of comparison_prop
	for object: Object in array:
		var prop_value = object.get(comparison_prop)
		if split.has(prop_value):
			split[prop_value].append(object)
		else:
			split[prop_value] = [object]
	var prop_values = split.keys()
	# Find the order the groups should have
	prop_values.sort()
	var ret = []
	# Merge the groups in order
	for p in prop_values:
		ret.append_array(split[p])
	return ret