Re: [xml] XPath optimizations

[Bjorn Reese <breese mail1 stofanet dk>]

Petr Pajas wrote:

>    glance). I've replaced Shell's sort with Bubble sort. As everyone
>    knows its complexity is between O(n) and O(n^2), which is the worst
>    case (inverted list) and of course worse than Shell's sort in
>    average case. How ever, in case of presorted node-list, bubble sort
>    always compares two subsequent nodes in the list in which case
>    xmlXPathCmpNodes does not go far when traversing the tree and is
>    O(1). (Both Shell's sort and quick-sort usually compares nodes far
>    in the list, so xmlXPathCmpNodes has far journeys pretty often).
>    Since in most cases, XPath results *are* actually already well
>    sorted (and I can hardly imagine an expression resulting in a long
>    reversely ordered node-list), bubble sort seems much better choice

Here's a suggestion. Before doing the actual sorting, examine N nodes.
If they (or most of them) are in increasing order, we will use Bubble
sort, otherwise we use Shell's sort.