import random
import time

class SortTimer:
    """
    This class times, in both actual time taken and number of steps taken for
    each, merge sort and insertion sort.
    """
    def __init__(self, seed = 0):
        self.steps = 0
        self.seed = seed

    def time_sorts(self):
        """
        Runs both insertion sort and merge sort on a random list of 10240
        integers all between 1 and 2**16.  For repeatability, a seed can be
        given to self upon construction for the random list.
        """
        #Keep in mind that steps should be reset to 0 between sorts!
        self.steps = 0

        if self.seed == 0:
            random.seed()
        else:
            random.seed(self.seed)

        #Fancy syntax for building a list of random items
        items = [random.randint(1, 2**16) for x in range(10240)]

        time_before = time.time()
        merge_sorted = self.merge_sort(items[:])
        total_time = time.time() - time_before
        print 'steps for merge sort:', self.steps
        print 'real time for merge sort:', total_time

    def merge(self, list1, list2):
        """
        Merges the sorted lists list1 and list2 into one single sorted list.
        """
        i = 0
        j = 0
        merged = []

        while i < len(list1) and j < len(list2):
            # each comparision in merge sort is counted . . .
            self.steps += 1
            if list1[i] < list2[j]:
                merged += [list1[i]]
                i += 1
            else:
                merged += [list2[j]]
                j += 1

        return merged + list1[i:] + list2[j:]

    def merge_sort(self, items):
        """
        Sorts the list items via merge sort.
        """
        if len(items) == 1:
            return items

        # . . . as well as each split
        self.steps += 1
        sorted1 = self.merge_sort(items[:len(items)/2])
        sorted2 = self.merge_sort(items[len(items)/2:])

        return self.merge(sorted1, sorted2)