import random
import time
import sys

def partition(L, first, last):
    swap(L, first, random.randint(first, last))
    # We pick the element L[first] as the "pivot" around which we partition the list
    p = first

    # We process the rest of the elements, one-by-one, in left-to-right order
    for current in range(p+1, last+1):
        # If L[current] is smaller than the pivot, it needs to move into the first block,
        # to the left of the pivot. 
        if L[current] < L[p]:
            swap(L, current, p+1)
            swap(L, p, p+1)
            p = p + 1

    return p

def generalQuickSort(L, first, last):
    # Base case: if first == last, then there is only one element in the
    # slice that needs sorting. So there is nothing to do.

    # Recursive case: if there are 2 or more elements in the slice L[first:last+1]
    if first < last:
        # Divide step: partition returns an index p such that 
        # first <= p <= last and everthing in L[first:p] is <= L[p]
        # and everything in L[p+1:last+1] is >= L[p]
        p = partition(L, first, last)

        # Conquer step
        generalQuickSort(L, first, p-1)
        generalQuickSort(L, p+1, last)

        # Combine step: there is nothing left to do!

def quickSort(L):
    generalQuickSort(L, 0, len(L)-1)

def swap(L, i, j):
    temp = L[i]
    L[i] = L[j]
    L[j] = temp


def selectionSort(L):
    n = len(L)

    for i in range(n):
        m = min(L[i:])
        j = i + L[i:].index(m)
        swap(L, i, j)

    return L

# Assumes that L[first:mid+1] is sorted and also
# that L[mid: last+1] is sorted. Returns L with L[first: last+1] sorted

def merge(L, first, mid, last):
    
    i = first # index into the first half
    j = mid + 1 # index into the second half

    tempList = []
    
    # This loops goes on as long as BOTH i and j stay within their
    # respective sorted blocks
    while (i <= mid) and (j <= last):
        if L[i] <= L[j]:
            tempList.append(L[i])
            #print L[i], "from the first block"
            i += 1
        else:
            tempList.append(L[j])
            #print L[j], "from the second block"
            j += 1
            
    # If i goes beyond the first block, there may be some elements
    # in the second block that need to be copied into tempList.
    # Similarly, if j goes beyond the second block, there may be some
    # elements in the first block that need to be copied into tempList
    if i == mid + 1:
        tempList.extend(L[j:last+1])
        #print L[j:last+1], "some elements in second block are left over"
    elif j == last+1:
        tempList.extend(L[i:mid+1])
        #print L[i:mid+1], "some elements from first block are left over"
        
    L[first:last+1] = tempList
    #print tempList
    

# The merge sort function; sorts the sublist L[first:last+1]    
def generalMergeSort(L, first, last):
    # Base case: if first == last then it is already sorted
    
    # Recursive case: L[first:last+1] has size 2 or more
    if first < last:
        # divide step
        mid = (first + last)/2
        
        # conquer step
        generalMergeSort(L, first, mid)
        generalMergeSort(L, mid+1, last)
        
        # combine step
        merge(L, first, mid, last)
        #print L[first:last+1], L
        
        
# Wrapper function
def mergeSort(L):
    generalMergeSort(L, 0, len(L)-1)
        

#Main Program
sys.setrecursionlimit(100000)
# Create random list
#N = 100000
N = 10000
L = []
LCopy = []
for i in range(N):
    #x = random.randint(1, 1000000)
    x = i
    L.append(x)
    LCopy.append(x)
print "Finished constructing the lists..."

startTime = time.time()
mergeSort(L)
endTime = time.time()
print "Time for Merge Sort is: ", endTime - startTime


startTime = time.time()
quickSort(LCopy)
endTime = time.time()
print "Time for Quick Sort is: ", endTime - startTime