py: Make list.sort keep stack usage within O(log(N)) bound.

Also fix list.sort so it works with user-defined types, and parse the
keyword arguments properly.

Addresses issue #338.

1 files changed, 21 insertions, 0 deletions

diff --git a/tests/basics/list_sort.py b/tests/basics/list_sort.py
index e323ff1c2..c185ddcd1 100644
--- a/tests/basics/list_sort.py
+++ b/tests/basics/list_sort.py
@@ -26,3 +26,24 @@ l.sort(reverse=False)
 print(l)
 print(l == sorted(l, reverse=False))
 
+# test large lists (should not stack overflow)
+l = list(range(2000))
+l.sort()
+print(l[0], l[-1])
+l.sort(reverse=True)
+print(l[0], l[-1])
+
+# test user-defined ordering
+class A:
+    def __init__(self, x):
+        self.x = x
+    def __lt__(self, other):
+        return self.x > other.x
+    def __repr__(self):
+        return str(self.x)
+l = [A(5), A(2), A(1), A(3), A(4)]
+print(l)
+l.sort()
+print(l)
+l.sort(reverse=True)
+print(l)