sortstuff.py

#!/usr/bin/env python3
import random

def msort(array, compare):
    l = len(array)
    if l > 2:
        mid = l//2
        left = msort(array[:mid], compare)
        right = msort(array[mid:], compare)
        return merge(left, right, compare)
    elif l == 2:
        a, b = array
        if compare(a,b):
            return [a,b]
        else:
            return [b,a]
    else:
        return array
        
def merge(left, right, compare):
    out = []
    while left and right:
        if compare(left[0],right[0]):
            out.append(left.pop(0))
        else:
            out.append(right.pop(0))
    out.extend(left)
    out.extend(right)
    return out

def qsort(array, compare):
    if array:
        p = random.randint(0, len(array)-1) # pick a random element
        pivot = array[p]
        left, right = [], []
        for i, x in enumerate(array):
            if i != p: # skip the pivot
                if compare(x,pivot):
                    left.append(x)
                else:
                    right.append(x)

        left, right = qsort(left, compare), qsort(right, compare)
        return left + [array[p]] + right
    else:
        return array


def random_array(l):
    a = list(range(l))
    random.shuffle(a)
    return a 

def lt(a,b):
    return a <= b

def random_string_array():
    array = list("The cat likes the robot THE ROBOT LIKES THE CAT".split())
    random.shuffle(array)
    return array 

def lower_lt(a,b):
    return a.lower() <= b.lower()
    
if __name__ == '__main__':
    print("Numbers")
    a = random_array(20)
    print("In",a)
    print("Python Sort", sorted(a))
    print("Merge Sort", msort(a, lt))
    print("Quick Sort", qsort(a, lt))



    print("Strings")
    a = random_string_array()
    print("In",a)
    print("Python Sort", sorted(a, key=lambda x:x.lower()))
    print("Merge Sort", msort(a, lower_lt))
    print("Quick Sort", qsort(a, lower_lt))