Re: [xslt] Re: xsl:key degenerate performance

[Marc-Antoine Parent <maparent acm org>]

Hello! I just looked at the sort routine and found out it was a shell 
sort. Good enough for most cases; but on an already sorted list it 
indeed has a cost.
How about exploiting some alternative, faster sorting algorithms? 
Heapsort or Mergesort are generally faster than shell sort; and their 
worst case is acceptable, unlike quicksort.
A better option is an algorithm designed to be resilient to 
already-sorted lists, such as Smoothsort.
http://en.wikipedia.org/wiki/Smoothsort
If there is interest, I can propose an implementation.
Marc-Antoine