Commits

Lars Wassermann committed d02d002

(tfel, lwassermann) replaced inplace quicksort by rpython timsort in fieldtypes

Comments (0)

Files changed (1)

 from spyvm import model, shadow
 
 from rpython.rlib import objectmodel, jit, signature
+from rpython.rlib.listsort import TimSort
 
 class TypeTag():
     pass
 flt = TypeTag()
 obj = TypeTag()
 
+class FieldSort(TimSort):
+    def lt(self, a, b):
+        return a[0] < b[0]
+
 maps = {}
 
 class VarSizedFieldTypes():
     def ascent(self, changes):
         parent = self.parent
         if parent is None:
-            sort(changes)
+            FieldSort(changes).sort()
             return self.descent(changes)
         else:
             change = self.diff
             return typer
     except AttributeError:
         return nilTyper
-
-def sort(an_array):
-    end = len(an_array) - 1
-    sort_quick_inplace(an_array, 0, end)
-
-
-def sort_quick_inplace(an_array, start, end):
-    assert start >= 0 and end < len(an_array)
-
-    def partition(an_array, start, end):
-        key = an_array[start][0]
-        i = start - 1
-        j = end + 1
-        while True:
-            i += 1
-            j -= 1
-            while not an_array[j][0] <= key:
-                j -= 1
-            while not an_array[i][0] >= key:
-                i += 1
-            if j <= i:
-                return j
-            else:
-                an_array[i], an_array[j] = an_array[j], an_array[i]
-
-    if start < end:
-        mid = partition(an_array, start, end)
-        sort_quick_inplace(an_array, start, mid)
-        sort_quick_inplace(an_array, mid + 1, end)