matchfuzzypos sort is "unstable"

[Maxim Kim]

The plugin I do https://github.com/habamax/vim-select uses ripgrep to feed files into fuzzymatchpos function. It looks good for me with one minor issue with sorting, have a look into the video I have recorded:

https://youtu.be/RPM3GccvDGA

What is happening there:

1. I ran `rg --files --no-ignore-vcs --hidden --glob !.git` in a job

2. On out_cb handler I update the buffer with the files

3. You can see ordering of the same files is constantly changed -- I believe it shouldn't be like this, but not 100% sure.

So should the order or sort of the matchfuzzypos result be the same on the second, third etc run? The data matchfuzzypos operates on is constantly increasing but the output (top) is the same only sorted a bit differently.

[Maxim Kim]

Note that for the same set of files and input on wsl vim I get "stable" sorted output.

[Yegappan Lakshmanan]

Hi,

The matchfuzzy() function uses the standard C library qsort() function to sort the

matches by score. The qsort() function is not guaranteed to be stable as explained

in the following page;

https://nullprogram.com/blog/2014/08/29/#:~:text=Since%20quicksort%20is%20an%20unstable,has%20no%20stable%20sort%20function.

So the list of strings passed to the matchfuzzy() function with the same matching

score are not guaranteed to retain the same order in the returned list.

Note that if you call the matchfuzzy() function multiple times with different

number of strings, then their matching scores may be different and the

returned list may have a different order for the strings.

- Yegappan

[Dominique Pellé]

Yegappan Lakshmanan wrote:

> The matchfuzzy() function uses the standard C library qsort() function to sort the
> matches by score. The qsort() function is not guaranteed to be stable as explained
> in the following page;
>
> https://nullprogram.com/blog/2014/08/29/#:~:text=Since%20quicksort%20is%20an%20unstable,has%20no%20stable%20sort%20function.
>
> So the list of strings passed to the matchfuzzy() function with the same matching
> score are not guaranteed to retain the same order in the returned list.

qsort() is not stable, but can't we have a tie-breaker
in its comparator fuzzy_item_compare() to make it
stable when multiple entries have the same score?
(e.g. when scores are equal, compare by string).

Regards
Dominique