# sorts.py
#    Implementations of selection sort and merge sort.

def selSort(lst):
    n = len(lst)
    for bottom in range(n-1):
        mp = bottom
        for i in range(bottom+1,n):
            if lst[i] < lst[mp]:
                mp = i
        lst[bottom], lst[mp] = lst[mp], lst[bottom]

def merge(lst1, lst2, lst3):
    # merge sorted lists lst1 and lst2 into lst3
    # these indexes keep track of current position in each list
    i1 = i2 = i3 = 0
    n1, n2 = len(lst1), len(lst2)

    # Loop while both pieces have data
    while i1 < n1 and i2 < n2:
        if lst1[i1] < lst2[i2]:     # copy from lst1
            lst3[i3] = lst1[i1]     
            i1 = i1 + 1
        else:                       # copy from list2
            lst3[i3] = lst2[i2]     
            i2 = i2 + 1
        i3 = i3 + 1                 # item added to lst3

    # Here either lst1 or lst2 is done, One of the following loops will
    # execute to finish up the merge.
    
    # Copy remaining items (if any) from lst1
    while i1 < len(lst1):
        lst3[i3] = lst1[i1]
        i1 = i1 + 1
        i3 = i3 + 1
    # Copy remaining items (if any) from lst2
    while i2 < len(lst2):
        lst3[i3] = lst2[i2]
        i2 = i2 + 1
        i3 = i3 + 1

def mergeSort(lst):
    # Put items of lst in ascending order
    n = len(lst)
    # Do nothing is lst contains 0 or 1 items
    if n > 1:
        # split into two sublists
        m = n / 2
        lst1, lst2 = lst[:m], lst[m:]
        # recursively sort each piece
        mergeSort(lst1)
        mergeSort(lst2)
        # merge the sorted pieces
        merge(lst1, lst2, lst)


## Functions for timing sorts
        
## Example:
## >>> from sorts import *
## >>> timingCurve(mergeSort, 1000, 2000, 5000, 5)
## List size:  1000
## 0
## 1
## 2
## 3
## 4
## avg = 0.2
## List size:  3000
## 0
## 1
## 2
## 3
## 4
## avg = 0.8
## [0.234578800201, 0.765318417549]

import random, time

def genList(n):
    # RETURNS a list of n random floats
    xs = []
    for i in range(n):
        xs.append(random.random())
    return xs

def timeSort(sortFn, n):
    # RETURNS the time it takes to sort a random list of size n
    #    using the given sorting function sortFn
    xs = genList(n)
    t1 = time.time()
    sortFn(xs)
    t2 = time.time()
    return t2 - t1

def timingCurve(sortFn, start, inc, stop, trials):
    # RETURNS a list representing the average time required to sort
    #     lists of sizes start, start+inc, start+2*inc, ..., stop.
    times = []
    for n in range(start, stop, inc):
        print "List size: ", n
        sum = 0.0
        for i in range(trials):
            print i
            sum = sum + timeSort(sortFn,n)
        avg = sum / trials
        print "avg = %0.1f" %(avg)
        times.append(avg)
    return times