--- a/jaxp/src/com/sun/org/apache/xalan/internal/xsltc/dom/DupFilterIterator.java	Thu Apr 12 08:38:26 2012 -0700
+++ b/jaxp/src/com/sun/org/apache/xalan/internal/xsltc/dom/DupFilterIterator.java	Tue Apr 17 11:17:59 2012 -0700
@@ -88,7 +88,9 @@
         if (_isRestartable) {
             // KeyIndex iterators are always relative to the root node, so there
             // is never any point in re-reading the iterator (and we SHOULD NOT).
-            if (_source instanceof KeyIndex
+            boolean sourceIsKeyIndex = _source instanceof KeyIndex;
+
+            if (sourceIsKeyIndex
                     && _startNode == DTMDefaultBase.ROOTNODE) {
                 return this;
             }
@@ -100,7 +102,12 @@
                 while ((node = _source.next()) != END) {
                     _nodes.add(node);
                 }
-                _nodes.sort();
+
+                // Nodes produced by KeyIndex are known to be in document order.
+                // Take advantage of it.
+                if (!sourceIsKeyIndex) {
+                    _nodes.sort();
+                }
                 _nodesSize = _nodes.cardinality();
                 _current = 0;
                 _lastNext = END;