school

thing1's amazing school repo
Log | Files | Refs | Submodules | README

merge.py (808B)

      1 def sort(list):
      2     length = len(list)
      3     l1 = []
      4     l2 = []
      5     for i in range(length):
      6         if i >= (length / 2):
      7             l2.append(list[i])
      8         else:
      9             l1.append(list[i])
     10     if length > 2:
     11         l1 = sort(l1)
     12         l2 = sort(l2)
     13     return merge(l1, l2)
     14 
     15 
     16 def merge(l1, l2):
     17     i = 0
     18     j = 0
     19     output = []
     20     while i < len(l1) and j < len(l2):
     21         if l1[i] < l2[j]:
     22             output.append(l1[i])
     23             i += 1
     24         else:
     25             output.append(l2[j])
     26             j += 1
     27 
     28     while i < len(l1):
     29         output.append(l1[i])
     30         i += 1
     31     while j < len(l2):
     32         output.append(l2[j])
     33         j += 1
     34     return output
     35 
     36 
     37 if __name__ == "__main__":
     38     # call split on the list, will return  a sorted one
     39     print(sort([1, 4, 2, 4, 2, 5, 6, 2, 7]))