CS 371: Module 15: Exercise 1 (2 Points)

Developed by Professor Tralie and Professor Mongan.

Exercise Goals

The goals of this exercise are:
  1. Implement merge sort
  2. Implement a divide and conquer algorithm

Finish the code below to complete merge sort.

Enter your Ursinus netid before clicking run. This is not your ID number or your email. For example, my netid is ctralie (non Ursinus students can simply enter their name to get this to run, but they won't get an e-mail record or any form of credit)

Netid
Clicking Run below will check your work and, if it passes, will submit your work automatically. You must be connected to the VPN for submission to be successful! You will receive a copy of your code via e-mail, so you'll know that it was submitted if you receive that e-mail! VPN access requires Multi-Factor Authentication, which sends you a code when you log into the network. Instructions on configuring these for your account can be found here.

Merge

def swap(arr, i, j):
temp = arr[i]
arr[i] = arr[j]
arr[j] = temp
def merge(x, y, i1, mid, i2):
"""
Perform a merge of two contiguous sorted sub-chunks of
the array x, using y as a staging area
Parameters
----------
x: list
The main array
y: list
The array to copy into as the two chunks are being merged
i1: int
Left of first chunk
mid: int
Right of first chunk
i2: int
End of second chunk
"""
i = i1
j = mid+1
idx = 0
while i != mid+1 and j != i2+1:
if x[i] < x[j]:
y[idx] = x[i]
i += 1
else:
y[idx] = x[j]
j += 1
idx += 1
## TODO: Copy over any elements that are left in
## the first chunk
## TODO: Copy over any elements that are left in
## the second chunk
# Copy our merged sorted chunk from the staging area
# back into the chunk from i1 to i2
for idx in range(i2-i1+1):
x[i1+idx] = y[idx]
def mergesort_rec(x, y, i1, i2):
"""
A recursive call to sort a subset of the array
Parameters
----------
x: list
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Test Code Block

arr = [51, 21, 66, 69, 56, 13, 44, 6]
mergesort(arr)
print(arr, end='.')
arr = [23, 1, 15, 24, 47, 29]
mergesort(arr)
print(arr)
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Output

הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX