```1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 ``` ```#!/usr/bin/python3   # SI 335: Computer Algorithms # Unit 2   import random import sys from copy import copy   def swap(A, i, j):     A[i], A[j] = A[j], A[i]   def selectionSort(A):     for i in range(0, len(A)-1):         m = i         for j in range(i+1, len(A)):             if A[j] < A[m]:                 m = j         swap(A, i, m)   def insertionSort(A):     for i in range(1, len(A)):         j = i - 1         while j >= 0 and A[j] > A[j+1]:             swap(A, j, j+1)             j = j - 1   def selectionSortRec(A, start=0):     if (start < len(A) - 1):         m = minIndex(A, start)         swap(A, start, m)         selectionSortRec(A, start + 1)   def minIndex(A, start=0):     if start >= len(A) - 1:         return start     else:         m = minIndex(A, start+1)         if A[start] < A[m]:             return start         else:             return m   def mergeSort(A):     if len(A) <= 1:         return A     else:         m = len(A) // 2         B = A[0 : m]         C = A[m : len(A)]         mergeSort(B)         mergeSort(C)         A[:] = merge(B, C)   def merge(B, C):     A = []     i, j = 0, 0     while i < len(B) and j < len(C):         if B[i] <= C[j]:             A.append(B[i])             i = i + 1         else:             A.append(C[j])             j = j + 1     while i < len(B):         A.append(B[i])         i = i + 1     while j < len(C):         A.append(C[j])         j = j + 1     return A   # This is provided for testing purposes. def randomArray(size, maxval):     return random.sample(range(maxval), size)   def sortTest(algs = (selectionSort, insertionSort, selectionSortRec, mergeSort)):     sys.setrecursionlimit(10000)     allgood = True     data = randomArray(500, 1000000)     for alg in algs:         good = True         thisdata = copy(data)         alg(thisdata)         # check if it's sorted         for i in range(1, len(thisdata)):             if thisdata[i] < thisdata[i-1]:                 good = False         if set(thisdata) != set(data):             good = False         if not good:             print("FAILED CHECK FOR", alg.__name__)             allgood = False     if allgood:         print("Passed all sorting checks")   if __name__ == '__main__':     sortTest()```