X-Git-Url: https://code.kerkeslager.com/?p=sandbox;a=blobdiff_plain;f=sort2.py;fp=sort2.py;h=c08072d538d08d18ea71c084846f0f7f09afe2dd;hp=0000000000000000000000000000000000000000;hb=968af6bc53d70e889bae92c15606212c084e0168;hpb=45ec9c36ab7241cee93e615b3c901b5b80aa7aff

diff --git a/sort2.py b/sort2.py
new file mode 100644
index 0000000..c08072d
--- /dev/null
+++ b/sort2.py
@@ -0,0 +1,69 @@
+def merge(x:list, a:int, b:int, c:int):
+    if b == c:
+        return
+    while a < b and x[a] < x[b]:
+        a += 1
+
+    if a == b:
+        return
+    while b < c and x[b - 1] < x[c - 1]:
+        c -= 1
+
+    w = min(b - a, c - b)
+
+    tmp = x[b - w:b]
+    x[b - w:b] = x[b:b + w]
+    x[b:b + w] = tmp
+
+    merge(x, a, b - w, b)
+    merge(x, b, b + w, c)
+    merge(x, a, b, c)
+
+def getrun(x:list, a:int, depth:int):
+    if a == len(x):
+        return a
+
+    if depth == 0:
+        b = a + 1
+
+        while b < len(x) and x[b - 1] < x[b]:
+            b += 1
+
+        return b
+
+    b = getrun(x, a, depth - 1)
+    c = getrun(x, b, depth - 1)
+    merge(x, a, b, c)
+    return c
+
+def sort(x:list):
+    depth = 0
+    a = 0
+    b = getrun(x, a, depth)
+    c = getrun(x, b, depth)
+    merge(x, a, b, c)
+
+    while c < len(x):
+        depth += 1
+        b = c
+        c = getrun(x, b, depth)
+        merge(x, a, b, c)
+
+def is_sorted(x:list) -> bool:
+    for i in range(len(x) - 1):
+        if x[i] >= x[i + 1]:
+            return False
+    return True
+
+if __name__ == '__main__':
+    import random, unittest
+
+    class SortTests(unittest.TestCase):
+        def test_sorts(self):
+            for i in range(100):
+                x = [i for i in range(25)]
+                random.shuffle(x)
+                sort(x)
+                self.assertTrue(is_sorted(x))
+
+    unittest.main()