code.kerkeslager.com Git - sandbox/blob - sort2.py

   1 def merge(x:list, a:int, b:int, c:int):
   2     if b == c:
   3         return
   4     while a < b and x[a] < x[b]:
   5         a += 1
   6
   7     if a == b:
   8         return
   9     while b < c and x[b - 1] < x[c - 1]:
  10         c -= 1
  11
  12     w = min(b - a, c - b)
  13
  14     tmp = x[b - w:b]
  15     x[b - w:b] = x[b:b + w]
  16     x[b:b + w] = tmp
  17
  18     merge(x, a, b - w, b)
  19     merge(x, b, b + w, c)
  20     merge(x, a, b, c)
  21
  22 def getrun(x:list, a:int, depth:int):
  23     if a == len(x):
  24         return a
  25
  26     if depth == 0:
  27         b = a + 1
  28
  29         while b < len(x) and x[b - 1] < x[b]:
  30             b += 1
  31
  32         return b
  33
  34     b = getrun(x, a, depth - 1)
  35     c = getrun(x, b, depth - 1)
  36     merge(x, a, b, c)
  37     return c
  38
  39 def sort(x:list):
  40     depth = 0
  41     a = 0
  42     b = getrun(x, a, depth)
  43     c = getrun(x, b, depth)
  44     merge(x, a, b, c)
  45
  46     while c < len(x):
  47         depth += 1
  48         b = c
  49         c = getrun(x, b, depth)
  50         merge(x, a, b, c)
  51
  52 def is_sorted(x:list) -> bool:
  53     for i in range(len(x) - 1):
  54         if x[i] >= x[i + 1]:
  55             return False
  56     return True
  57
  58 if __name__ == '__main__':
  59     import random, unittest
  60
  61     class SortTests(unittest.TestCase):
  62         def test_sorts(self):
  63             for i in range(100):
  64                 x = [i for i in range(25)]
  65                 random.shuffle(x)
  66                 sort(x)
  67                 self.assertTrue(is_sorted(x))
  68
  69     unittest.main()