Optimize PathSelector mergeSortedSequences

[DrRataplan]

trafficstars

This function merges locally sorted sequences, it does this using a merge sort algorithm. For the case of ['path', ['descendant-or-self', ...], ['child', ...]], the sequences are even always globally sorted on the first result. We should be able to use this to our advantage, preventing a sort for the first item.

Because the ordering of further items in the separate sequences are not guaranteed to be in the global ordering, we would have to use position compares at a later point, but only up to the sequence from which we have yielded.

The current implementation forces a full document scan for queries like (//*)[1], because it is compiled to (/descendant-or-self::*/child::*)[1]. The new implementation would make it of constant complexity, yielding the very first node.

Another optimization would be rewriting (//*) to (/descendant::*), but the better sorting approach would also apply to all queries like (/descendant::elementName/parent::parentName).

This rule should apply to all expressions of the form [sorted]/[peer], but not for expressions of the form [sorted]/[subtree]: (/descendant::*/descendant::*[last()])[1] != (/descendant::*!descendant::*[last()])[1]