In place Merge Sort

merge-sort.py

from random import shuffle
from time import time


def compare(a, b):
    if a > b: return 1
    if a < b: return -1
    return 0


def less(a, b):
    return compare(a, b) < 0


def merge(arr, aux, lo, mid, hi):
    # Copy array positions to auxillary
    # that we care about to aux so
    # we can sort in place
    # + 1 because we subtracted for
    # aux creation and indexing
    for i in xrange(lo, hi + 1): aux[i] = arr[i]

    # The beginning of the left half
    i = lo

    # The beginging of the right half
    j = mid + 1

    # Counter for iterating over entire array
    # and placing the sorted value
    k = lo

    # Iterate until we have completed the entire
    # Array size of the 2 problems
    # Because python requires an xrange for basic
    # iteration using for loops, use a while instead
    while k <= hi:
        # Check if left half is done merging
        if i > mid:
            # merge in the rest of the right half
            arr[k] = aux[j]
            j += 1

        # Check if right half is done merging
        elif j > hi:
            # merge in the rest of the left half
            arr[k] = aux[i]
            i += 1

        # neither half is done merging
        # Check if left half is less than right
        elif less(aux[i], aux[j]):
            # left half is less, merge it in
            arr[k] = aux[i]
            i += 1

        # neither half done merging still
        # but current right is smaller
        else:
            arr[k] = aux[j]
            j += 1

        k += 1


# exposed method for sorting
def sort(arr):
    n = len(arr)

    # In order to sort in place
    # need an auxillary array for storing
    # halfed arrays values
    aux = [None] * n
    _sort(arr, aux, 0, n - 1)


def _sort(arr, aux, lo, hi):
    # Check if hi is equivalent or less than lo
    # because there is no array to divide at that point
    if hi <= lo: return

    # Grab mid point of 2 arrays
    mid = lo + (hi - lo) / 2

    # Sort lower half of array recursively
    _sort(arr, aux, lo, mid)

    # Sort upper half recursively
    _sort(arr, aux, mid + 1, hi)

    # Merge recursively
    merge(arr, aux, lo, mid, hi)

class Timer:
    def __init__(self):
        self.now = time()

    def delta(self):
        return time() - self.now


def is_sorted(arr):
    for i in xrange(len(arr)):
        if less(arr[i], arr[i - 1]): return False
    return True


if __name__ == "__main__":
    a = range(1000)
    shuffle(a)

    t = Timer()
    sort(a)
    d = t.delta()

    assert is_sorted(a), "Array not sorted"
    print "Time to sort %f seconds" % d