warn the user when the custom sort function isn't consistent

[volzhs]

not always, but very often crashed on Windows 7.

extends Node2D

func _ready():
    randomize()

    for i in range(20):
        var list = range(10)
        list.sort_custom(self, "shuffle_array")
        print(list)

func shuffle_array(a, b):
    return randi() % 2 == 0

I ran this code 20 times on Windows 7. 8 times good, and 12 times crashed.

1 of 30 crashed on Ubuntu 14.04.

and one more weird thing is sometimes element is missing.

    for i in range(10): # changed 20 to 10
        var list = range(10)
        list.sort_custom(self, "shuffle_array")
        print(list)

this is on Windows 7.

9, 8, 4, 3, 2, 1, 6, 5, 7, 0
9, 8, 6, 5, , 0, 3, 1, 4, 7    > "2" is gone
8, 7, 4, 3, 6, 2, 0, 9, 1, 5
9, 5, 4, 3, 2, , 6, 8, 7, 0    > "1" is gone
9, 8, 7, 6, 2, 1, 0, 3, 4, 5
9, 8, 7, 6, 5, 0, 3, 1, 2, 4
4, , 2, 0, 8, 6, 9, 5, 7, 3    > "1" is gone
9, 8, 7, 5, 2, 0, 1, 3, 6, 4
7, 6, 1, 0, 4, 2, 8, 9, 5, 3
9, 7, 6, 4, 3, 2, 1, 0, 8, 5

this is on Ubuntu 14.04

8, 3, 2, 1, 0, 5, 7, 4, 6, 9
8, 6, 5, [], 1, 0, 2, 4, 7, 9
8, 6, 5, [], [], 0, 3, 4, 7, 9
9, 8, 7, 6, 4, 3, 2, 1, 0, 5
9, 8, 6, 5, 4, 2, 7, 0, 1, 3
8, 6, 5, 9, 4, 3, 7, [], 0, 2
5, 3, 2, 1, 0, 6, 4, 8, 7, 9
9, 6, 4, 2, 3, 7, [], 0, 5, 8
7, 6, 5, 4, 9, 2, 1, 0, 3, 8
7, 3, 2, 1, 6, 0, 4, 5, 8, 9

[bojidar-bg]

I bet the problem comes for the fact that the algorithm was designed with constant compare functions in mind, not some that return a random number...

[vnen]

I believe it uses the Heapsort algorithm and it indeed assumes that the comparison function is consistent.

Sorting is not a good method to shuffle an array anyway. There are solutions that runs in O(n).

[volzhs]

I changed way to shuffle array to work correctly. It's up to godot dev team to close this issue if I shouldn't do this way and it's not a bug.

[bojidar-bg]

@volzhs You can change the issue to a request to warn the user when the function used isn't consistent (only in debug mode).

[vnen]

I'm not sure how the comparison function can be tested for consistency (or even if it should be). But I agree that crashing is never good.