--- /dev/null
+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()