# merge sort: split list in half, then sort each half and
# merge the two; this is done recursively
#
# we print the current state of the list each time through
#
# also count (and print) the number of comparisons and
# exchanges
#
# Matt Bishop ECS 36A, Winter 2019
#
#
# set this to False to print *only* the original (unsorted)
# and the final (sorted) lists
# set to True to print the intermediate (partially sorted) lists
#
showintermediate = True
#
# we will generate a list of this many numbers
# and then shuffle them 7 times using shuffle()
# from the random module
#
import random
nnums = 20
# set the number of comparisons to 0
compares = 0
# swaps don't really make sense, so we count copies
copies = 0
#
# this is the merge sort routine
#
# if the list is 1 item, you are done
# otherwise, split the list in two parts, sort them independently
# (using mergesort), then merge the two lists
#
def mergesort(numlist):
# we track the number of comparisons and swaps (exchanges)
global copies, compares
# if the list is one number, you're done
if len(numlist) <= 1:
# print the current state of the list (visually see the sorting)
if showintermediate:
print(" Merge:", numlist)
return
# find the midpoint of the list
mid = len(numlist) // 2
# split the list into 2 parts, left and right
# note midpoint in kept in the right half
left = numlist[:mid]
right = numlist[mid:]
# now sort each half
mergesort(left)
mergesort(right)
# here, i indexes left, j indexes right, and
# k indexes numlist
# left and right aremerged; their sorted merge
# is put in numlist
# start everything at the beginning of the lists
i = j = k = 0
# this part does the merge
# compare first element of left with first element
# of right; put the smaller into numlist and advance
# the appropriate indices
while i < len(left) and j < len(right):
# we do a compare and a copy here
compares += 1
copies += 1
# if left is smaller or equal, put it into numlist
if left[i] <= right[j]:
numlist[k] = left[i]
i += 1
k += 1
# if right is smaller, put it into numlist
elif left[i] > right[j]:
numlist[k] = right[j]
j += 1
k += 1
# at this point, either i or j is at the end so
# only one of the following while loops has its
# body executed
while i < len(left):
# a copy
copies += 1
# add next element of left to the end of numlist
numlist[k] = left[i]
i += 1
k += 1
while j < len(right):
# a copy
copies += 1
# add next element of left to the end of numlist
numlist[k] = right[j]
j += 1
k += 1
# print the current state of the list (visually see the sorting)
if showintermediate:
print(" Merge:", numlist)
#
# generate a list of numbers
# we just put the first nnums number into a list (0 .. nnums-1)
# and then shuffle it 7 times
#
def loadnums():
# generate the list; use range and convert it
numlist = list(range(nnums))
# now shuffle 7 times; in theory, this makes
# it as random as possible
for i in range(0, 7):
random.shuffle(numlist)
# and return the list!
return numlist
#
# this puts it all together
#
def main():
# we need to print these
global compares, copies
# get the list
# if it's empty, quit (just in case :)
nums = loadnums()
if nums == []:
return
# print the initial list
print("Unsorted:", nums)
# sort the list
mergesort(nums)
# print the sorted list and the relevant statistics
print(" Sorted:", nums)
print("This took {} comparisons and {} copies".format(compares, copies))
#
# and we're off!
#
main()