Hi @EnderNon, thanks for the report.

Analysis of map_icon.png: The palette sorting evaluations are all tied for best result. When this happens it chooses the one that was performed first.
In the first run, the luma sort is performed first and this is what is selected for the output. In the second run, the luma sort is skipped because it is the same as the input, so the battiato sort is selected instead. The input "baseline" is always evaluated last, so it is never preferred in the case of a tie and is why a second run may give a different result. A third run would end up the same as the first and can therefore never produce further improvement.

I'll have to consider if there's anything we can improve here but my initial thought is to just keep it as-is. If we were to change it to, e.g., prefer the input baseline in the case of a tie, then you would be stuck with the first result and never achieve the smaller size of the second run.

A somewhat naive initial idea I'm thinking is that choosing one of the tied sorts at random, or from some tuned probability distribution, could be an improvement overall if the expected final size is less than just always sticking with the first, but doing that comes with its own set of gotchas related to reproducibility... Perhaps there is something better than that though.

Maybe, if running multi-threaded anyway, run all of these tied (& close-to-tied) palette sorts in parallel? Kinda like CPUs do predictive branching?

A somewhat naive initial idea I'm thinking is that choosing one of the tied sorts at random, or from some tuned probability distribution, could be an improvement overall if the expected final size is less than just always sticking with the first, but doing that comes with its own set of gotchas related to reproducibility... Perhaps there is something better than that though.

Yeah, determinism is important. Perhaps we could just adjust the order so that, e.g. mzeng is preferred if we know it's usually the best one.

Maybe, if running multi-threaded anyway, run all of these tied (& close-to-tied) palette sorts in parallel? Kinda like CPUs do predictive branching?

Indeed, I still plan to get around to #523 someday...