import time def selectionSortInPlace(l, a): """Given a list of numbers and a starting index a, sorts the slice l[a:] (that is, the part of the list from index a onward) in place and returns nothing.""" while len(l) - a >= 2: # Scan to find smallest element. least = a for i in range(a + 1, len(l)): if l[i] < l[least]: least = i # Swap the list elements in positions a and least. temp = l[a] l[a] = l[least] l[least] = temp # The ath element is correct; sort the rest of the list. a += 1 return l def selectionSort(l): """Given a list of numbers, sorts the list using selection sort and returns the sorted list. Does not alter the input list.""" new = l[:] return selectionSortInPlace(new, 0) def mergeSort(l): """Given a list of numbers, sorts the list using merge sort and returns the sorted list. Does not alter the input list.""" if len(l) <= 1: # The list is so short that it is already sorted. return l else: # Sort the front and back halves of the list. middle = len(l) / 2 front = mergeSort(l[:middle]) back = mergeSort(l[middle:]) # Merge the two halves into a single sorted list. result = [] i = 0 j = 0 while i < len(front) and j < len(back): if front[i] < back[j]: result.append(front[i]) i += 1 else: result.append(back[j]) j += 1 # Include any remaining elements from the lists. while i < len(front): result.append(front[i]) i += 1 while j < len(back): result.append(back[j]) j += 1 return result def sortingTest(count, function): """Sorts a list of count integers using the given sorting function. Returns the time required to sort, in seconds.""" unsorted = range(count, 0, -1) startTime = time.time() sorted = function(unsorted) endTime = time.time() return endTime - startTime if __name__ == "__main__": l = [5, 2, 9, 1, 7, 3, 4, 6, 8, 0] print "The unsorted list is", l, "." print "The result of selectionSort() is", selectionSort(l), "." print "The result of mergeSort() is", mergeSort(l), "." print "The original list is still intact:", l, "." print "Here is a sorting test:" for i in range(1000, 11000, 1000): print i, sortingTest(i, selectionSort)