#!/usr/bin/env python
# coding: utf-8

# ## Merge Sort
# 
# ### Created by: Gargi, Theo
# ### Reviewed by: Joon

# In[ ]:


# This function is for testing, do not modify
def check(actual, expected):
    if expected != actual:
        print(
            f"Function should return the value {expected}, it is returning the value {actual}")
    else:
        print(f"Congratulations, the test case passed!")


# ### Exercise 1
# 
# Python3 has a built in sorting function that we can use for parts of this exercise.
#   
# Write a function ```sort4``` that sorts a list of 4 elements. The function should make two calls to ```sort2``` where `sort2` sorts a list of size 2.

# In[ ]:


sort2 = sorted


def sort4(L):
    L_first_sorted = sort2(L[0:2])
    L_last_sorted = sort2(L[2:4])
    #
    # do something to return a sorted list
    #


# In[ ]:


L = [5, 2, 1, 6]
check(sort4(L), [1, 2, 5, 6])

M = [4, 3, 2, 1]
check(sort4(L), [1, 2, 3, 4])


# ### Exercise 2
# 
# Write a function ```sort32``` that sorts a list of 32 elements. The function should make two recursive calls to a provided function ```sort16```

# In[ ]:


sort16 = sorted


def sort32(L):
    L_first_sorted = sort16(L[0:16])
    L_last_sorted = sort16(L[16:32])
    #
    # do something to return a sorted list
    #


# In[ ]:


# TEST_CASE
L = [32, 31, 30, 29, 28, 27, 26, 25, 24, 23, 22, 21, 20, 19, 18,
        17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1]

check(sort32(L), [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,S 26, 27, 28, 29, 30, 31, 32])


# ### Exercise 3
# 
# Write a function ```merge_sort``` that will sort a list of _any_ size. The function should make two recursive calls to itself 

# In[ ]:


def merge_sort(L):
    #
    # do something here
    #
    L_first_sorted = merge_sort(
        L[0:int(len(L)/2)])
    L_last_sorted = merge_sort(
        L[int(len(L)/2):len(L)])
    #
    # do something to return a sorted list


# In[ ]:


L = [23, 10, 5, 1, 4]
check(merge_sort(L), [1, 4, 5, 10, 23])

M = [4, 3, 2, 1]
check(merge_sort(M), [1, 2, 3, 4])


# ## Quick Sort

# ### Exercise 4
# 
# Sort by hand using the quicksort method the following list of numbers {4,7,8,10,1,2,5,9,3,6} showing all your steps. Use the following pivots 7, 2, 9, 4.

# In[ ]:


Write your answer here:


# ### Exercise 5
# Using quicksort, sort the following list of football teams based on their names. Try to write your own quicksort function based on the algorithm given in the lecture (below)
# 
# __Algorithm Quicksort:__ Input `L` of length `n`.
#     
# 1. Pick random `j` in `[0,...,n-1]`
# 
# 2. Let `x=L[j]` and reorder `L` so that locations `L[0],..,L[j-1]` are smaller than `x` and locations `L[j],...,L[n-1]` are at least as large as `x`.
# 
# 3. Recursively sort `L[0],...,L[j-1]` and `L[j+1],...,L[n-1]`

# In[ ]:


import random
L = ["Man United", "Leicester", "Chelsea", "Tottenham", "Arsenal",
     "Liverpool", "Southampton", "Man City", "Crystal Palace"]

# Write your solution here:


# ### Challenge: Exercise 6
# Using your quicksort algorithm, sort the following list of football teams based on their points.

# In[ ]:


L = [["Man United", 10],
     ["Leicester", 3],
     ["Chelsea", 6],
     ["Tottenham", 5],
     ["Arsenal", 7],
     ["Liverpool", 9],
     ["Southampton", 1],
     ["Man City", 10],
     ["Crystal Palace", 9]]

# Write your solution here: