Merge sort
  • Best Case, O(nlogn)
  • Worst Case, Ω(nlogn)
  • Memory Complexity, O(n)
    1. #!/usr/bin/python
    2.  
    3. import random
    4.  
    5. def merge_sort(l):
    6.     if len(l) <= 1:
    7.         return l
    8.  
    9.     # split
    10.     m = int(len(l)/2)
    11.     left = merge_sort(l[:m])
    12.     right = merge_sort(l[m:])
    13.  
    14.     # merge
    15.     merge = []
    16.     while left and right:
    17.         if left[0] < right[0]:
    18.             merge.append(left.pop(0))
    19.         else:
    20.             merge.append(right.pop(0))
    21.  
    22.     if left:
    23.         merge = merge + left
    24.  
    25.     if right:
    26.         merge = merge + right
    27.  
    28.     return merge
    29.  
    30. def get_list():
    31.     random.seed()
    32.     l = random.choices(range(10), k=10)
    33.  
    34.     return l
    35.  
    36. def main():
    37.     l = get_list()
    38.     print(l)
    39.  
    40.     l = merge_sort(l)
    41.     print(l)
    42.  
    43. if __name__ == '__main__':
    44.     main()
    45.