merge_sort.py

import random

count    = 10
max_rand = 100
min_rand = 0
lst = []

def merge_sort(lst):

    if len(lst) <= 1:
        return lst

    half = int(len(lst) / 2)
    left = lst[0:half]
    right = lst[half:]

    left = merge_sort(left)
    right = merge_sort(right)

    # Perform merge
    merged = []
    FIRST = 0
    while left and right:
        if left[FIRST] < right[FIRST]:
            merged.append(left.pop(FIRST))
        else:
            merged.append(right.pop(FIRST))

    if left:
        merged += left
    if right:
        merged += right

    return merged

for _ in range(count):
    x = random.randint(min_rand, max_rand)
    if x not in lst:
        lst.append(x)

print "Unsorted:      ", lst
print "Merge Sort:    ", merge_sort(lst)