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()