The different non-deterministic outputs actually end up with the different g values.

Sorting matches_by_j fixes the non-determinism but it doesn't fix the correctness. The correct result depends on the incremental l value being computed and I don't think there is a matches_by_j sort that has a connection to the correct result. What actually should be sorted is the iteration over for l, last_m of optimal.m[k - 1] (in bruteforce_update) but it should be sorted by last_m.g, this will ensure update() is called in the right order.

I actually ran into this with the passphrase "horse_correct_battery_staple" [sic]. For one reason or another, zxcvbn-cpp provoked a different (& incorrect) result than upstream
zxcvbn.

To verify this yourself, randomize the iteration of for l, last_m of optimal.m[k - 1] for different runs of "horse_correct_battery_staple" and you'll get different result sequences with different g values.

Originally posted by @rianhunter in dropbox/zxcvbn#158 (comment)