# Merge Sort vs Insertion Sort vs Bubble Sort example in Python
#
# Jay Summet
# CS 1301
# Donated to the public domain: March 2009

from random import *
import time

############################################
##  Insertion Sort in Python.
############################################
#
# The insertion sort will start with the 2nd element of the list
# and compare it to the first element. If it is smaller, it will
# slide the first element to the right and insert the smaller element
# at the beginning of the list. Once it's finished with the 2nd element,
# the first two elements in the list are in sorted order, and the rest
# of the list is still unsorted. So it moves on to the 3rd element
# of the list and starts sliding any elements in the sorted part of the
# list to the right until it finds the right spot to place the current
# element. It repeats this until the list is entirely sorted.
#
# Insertion sort is a O(N^2) algorithm, although in reality
# the average case running time is N^2 / 4.
#

def insertionSort(list2):
  for i in range(1, len(list2)):
     save = list2[i]
     j = i
     while j > 0 and list2[j - 1] > save:
        list2[j] = list2[j - 1]
        j = j - 1
     list2[j] = save


################################################################
################### Bubble Sort ################################
#
# Bubble Sort works by passing through the list of numbers and
# swapping any numbers that are not in sorted order.
# To guarantee that a list is sorted, this swapping pass must be
# repeated N-1 times.
#
# In this demo, I have separated the swapElements step from
# the repetition step into a helper function, but they could just
# as easily be combined.
#
# Because it takes N-1 comparisons to swap elements in the list,
# and you do this N-1 times, the time complexity of bubble sort
# is (n-1)*(n-1) or, simplifying, O(n^2)
#
def swapElements(aList):
    i  = 0
    while( i < len(aList) - 1 ):
        if (aList[i] > aList[i+1]):
            temp = aList[i]
            aList[i] = aList[i+1]
            aList[i+1] = temp
        i = i+1
           

def bubbleSort(aList):
    for num in range(len(aList) - 1 ):
        swapElements(aList)




###############################################################
################# Merge Sort ##################################
#
# Mergesort works by breaking the original list down into smaller
# and smaller sublists (until the sublists are of length 1).
# Then, it recursively merges sublists, keeping the resulting lists
# in sorted order.
# Merging two (already sorted) lists is an order N operation O(N).
#
# The number of merges performed is essentially Log N, because each
# step joins 1/2 of the remaining lists. In reality, the number of
# merges is large, but the majority of the merges do well less than N
# comparisons, and the big-O time complexity is O(N * Log N).
#

def merge(left,right):
    result = []
    i = 0
    j = 0
    while( i < len(left) and j < len(right) ):
        if(left[i] <= right[j]):
            result.append(left[i])
            i = i+1
        else:
            result.append(right[j])
            j = j+1
    result = result + left[i:]
    result = result + right[j:]
    return result


def mergeSort(aList):
        if len(aList) < 2:
                return(aList)

        middle = len(aList) / 2
        
        left = mergeSort( aList[:middle] )
        right = mergeSort( aList[middle:] )
        return merge(left,right)



#Generates a random list of numbers:
def randList(N):
        rList = []
        for x in range(N):
                rList = rList + [ randrange(0,N*2) ]

        return rList
                
ourList = randList(5000)

#Run bubble sort and merge sort on the same list of numbers:

#print ourList
print "List length is:", len(ourList)
timeStarted = time.time()
print "mergesort Started!"
mResult = mergeSort(ourList)
timeFinished = time.time()
print "mergesort Finished in", timeFinished - timeStarted ,"seconds.\n"


print "insertion sort Started!"
timeStarted = time.time()
insertionSort(ourList)
timeFinished = time.time()
print "insertion sort Finished in, ", timeFinished-timeStarted, "seconds.\n"


print "bubblesort Started!"
timeStarted = time.time()
bubbleSort(ourList)
timeFinished = time.time()
print "bubblesort Finished in, ", timeFinished-timeStarted, "seconds.\n"