Use the following psuedo code and definitions to complete a Python project:

Selection Sort

Pseudo-code

selectionSort(A) # A is an integer list/array

n=the size of A

# n = the number of integers in A

# same as n=len(A) in Python

# or n = |A|

# Pseudo-code syntaxes should be flexible

# but the meaning should be very clear

for i=0 to n-1

# same as for i in range(n): in Python

# or just for i=0, 1, ..., n-1

x = minimum in A[i:n] # or A[i, i+1, ..., n-1]

j = the index such that x=A[j]

if x

A[i], A[j] = A[j], A[i]

# or swap(A[i], A[j]

Merge Sort

merge(A1, A2): Takes two sorted lists A1 and A2, and outputs the sorted list including all

the elements of A1 and A2

Ex. What is the running time of merge(A1, A2) in terms of n1=#elements in A1 and

n2=#elements in A2? O(n1 + n2)

The Merge Sort Algorithm

1.

If n=1, just return A

2.

Otherwise split A into halves. Recursively sort each. Let the results be S1 and S2

3.

Return merge(S1, S2)

Pseudo-code

mergeSort(A)

n = |A|

if n <=1

return A

else

n1 = n / 2 where the fraction is rounded

S1, S2 = mergeSort(A[:n1]), mergeSort(A[n1:])

return merge(S1, S2)

***Problem***:

Complete the following definitions in Python USING THE SUMMAIRES ABOVE:

def selectionSort(intList): n=len(intList) #code the rest of selection sort

#until here

def merge(A1, A2): #A1 and A2 are sorted list. The function merges A1 with A2 # to return a single sorted list including all elements # start code here

# until here

def mergeSort(A): # This has to be a RECURSIVE function using merge(A1, A2) # - The grading script will check if it's recursive # start code here

# until here

***NOTE***

mergeSort must be a recursive function to call merge