PinChangeInt library- To attach interrupts to multiple Arduino (Uno/Mega) pins

I would rather let the programmer decide in which order he or she decides to add pins.

You have a point, and it should be made clear in the documentation that adding the most interrupted pin as first gives a better overall performance as it is found fastest.