custom_sort always returns errors once > 16 identical values are present in the array to be sorted

[2shady4u]

Godot version

3.3.2

System information

Windows 10

Issue description

Custom sorting an array of 16+ identical values returns several errors.

ERROR: partitioner: bad comparison function; sorting will be broken
   At: ./core/sort_array.h:183
ERROR: partitioner: bad comparison function; sorting will be broken
   At: ./core/sort_array.h:190
ERROR: unguarded_linear_insert: bad comparison function; sorting will be broken
   At: ./core/sort_array.h:263

Even if this array is extended with other non-identical values, the issue persists.

Steps to reproduce

Basically add more than 16 identical values to an array and try to sort them.
I used this minimal code example:

extends Node2D

static func sort(a : int, b : int) -> bool:
	if a > b:
		return false
	else:
		return true

func _ready():
	var array := []
	for _i in range(0, 17):
		array.append(0)
	array.sort_custom(self, "sort")

Minimal reproduction project

custom_sorting_error.zip

[Zireael07]

Just FYI, your zip didn't upload...

[2shady4u]

oops :/ will fix asap

[2shady4u]

Okay, I correctly uploaded my zip now 😃
Hopefully someone can confirm this now without any problem 😝

[akien-mga]

I can confirm the issue in 3.x (8028122) and master (e312df0).

(To compile on master, change last line to array.sort_custom(sort).)

There's indeed a 16 threshold number in SortArray:

godot/core/templates/sort_array.h

Line 57 in e312df0

INTROSORT_THRESHOLD = 16

But what it means and why it triggers this issue, I don't know.

I checked if it could be a false positive introduced by the validation checks from #15536 (added in 3.1), but in 3.0.6 the bug seems reproducible too: <= 16 works ok, 17 triggers an error spam with errors such as these, or crashes:

SCRIPT ERROR: sort: Invalid operands 'NodePath' and 'int' in operator '>'.
   At: res://Node2D.gd:4.
SCRIPT ERROR: sort: Invalid operands 'int' and '' in operator '>'.
   At: res://Node2D.gd:4.

SCRIPT ERROR: sort: Invalid operands 'Nil' and 'int' in operator '>'.
   At: res://Node2D.gd:4.
SCRIPT ERROR: sort: Invalid operands 'int' and '' in operator '>'.
   At: res://Node2D.gd:4.

[filipetavares]

I can confirm this still happens in 4.1.1 but in my case, this happens when there are more than 16 elements in an array, and the sort actually messes up the array previous order (but I'm guessing its because its not stable), as soon as I get the array to be lower than 16 elements it starts behaving correctly again.

For the moment I implemented a TimSort and I've solved my problem.
Just leaving the comment here to further bump this fix.

Keep up the good work.