Merge sort
  • Best Case, O(nlogn)
  • Worst Case, Ω(nlogn)
  • Memory Complexity, O(n)
  • #!/usr/bin/python
    
    import random
    
    def merge_sort(l):
        if len(l) <= 1:
            return l
    
        # split
        m = int(len(l)/2)
        left = merge_sort(l[:m])
        right = merge_sort(l[m:])
    
        # merge
        merge = []
        while left and right:
            if left[0] < right[0]:
                merge.append(left.pop(0))
            else:
                merge.append(right.pop(0))
    
        if left:
            merge = merge + left
    
        if right:
            merge = merge + right
    
        return merge
    
    def get_list():
        random.seed()
    
        l = []
        for i in range(10):
            l.append(random.choice(range(10)))
    
        return l
    
    def main():
        l = get_list()
        print(l)
    
        l = merge_sort(l)
        print(l)
    
    if __name__ == '__main__':
        main()