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

# # Week 3 Day 3 Morning Exercises
# 

# In[5]:


# 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!")


# ## 1
# ### 1.1
# Write a function `sort2` that sorts a list of numbers with a length of 2.

# In[8]:


def sort2(L):
    ## Your code goes here
    pass
    


# In[7]:


check(sort2([37, 9]), [9, 37])
check(sort2([1, 29]), [1, 29])


# ### 1.2
# 
# Write a function ```sort4``` that can sort a list of 4 elements. The function should make two calls to ```sort2``` where `sort2` sorts a list of size 2.

# In[2]:


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


# In[ ]:


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

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


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

# In[16]:


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, 26, 27, 28, 29, 30, 31, 32])


# ## 2
# ### 2.1
# Given the following two lists, can you write a small code using a while loop that can combine them into a single sorted list?

# In[9]:


list1 = [1, 3, 5, 7, 9]
list2 = [2, 4, 6, 8, 10]

## Your code goes below here


# ### 2.2
# What if we remove the last few elements from `list1`? What changes can you make for your code to work?

# In[10]:


list1 = [1, 3, 5, 7, 9]
list2 = [2, 4, 6]

## Your code goes below here


# ### 2.3
# Write a function `combine_sorted` that takes in two sorted lists and gives a combined sorted list.

# In[12]:


def combine_sorted(list1, list2):
    # Your code goes here
    pass


# ## 3
# 
# Write a function ```merge_sort``` that will sort a list of _any_ size. The function should make two recursive calls to itself and use the `combine_sorted` function you implemented in question 2.

# In[18]:


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
    return combine_sorted(L_first_sorted, L_last_sorted)


# 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])


# ## 4
# ### 4.1
# Write a function `sort_almost_sorted` that sorts a list whose first and second halves are already sorted. One such list is `L = [1, 3, 5, 7, 9, 2, 4, 6, 8, 10]`.

# In[ ]:





# ### 4.2
# Write a function `merge_sort2` that uses the previous function `sort_almost_sorted`. Instead of calling the function on smaller lists, it uses indices to keep track of where it is sorting.

# In[ ]:


def merge_sort2(L):
    return merge_sort2_h(L, 0, len(L) - 1)
def merge_sort2_h(L, start, end):
    #
    # do something here
    #
    
    ## define middle index
    ##mid = sth
    L = merge_sort2_h(L, start, mid)
    L = merge_sort2_h(L, mid + 1, end)
    #
    # do something to return a sorted list
    return sort_almost_sorted(L)