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

# # Merge Sort Exercises

# ![mergesortA.png](attachment:mergesortA.png)

# ![mergesortB.png](attachment:mergesortB.png)

# ### Question 1: Merge It! 

# #### Question 1.1 -- NO CODING!
# Here are two lists in sorted order:
# 
# ```
# L1 = [0,39]
# L2 = [6,90]
# ```
# 
# What is the result of creating a new, sorted list (with 4 numbers) that combines the numbers from both?
Type your answer here:
L3 = 
# #### Question 1.2 -- NO CODING!
# Repeat the same exercise for these two longer lists:
# ```
# L1 = [0,3,14,18,39,69,68,69,73,86,91,100]
# L2 = [6,7,10,24,32,65,78,80,87,94,97,99]
# ```
# What is the result of creating a new, sorted list that combines the numbers from both?
Type your answer here:
L3 = 
# #### Question 1.3 -- NO CODING!
# 
# It is possible to solve 1.1 and 1.2 by first combining the lists and then sorting them. Did you find a faster solution?
# 
# If you did not, ask your friend/person next to you to see if they did.
Type your answer here:

# #### Question 1.4 -- CODE!
# 
# Write a function `merge` that merges two sorted lists like you did above. 
# 
# - The inputs are `L1` and `L2`, two sorted lists
# - Return a new, sorted list that contains all the elements from both lists
# 
# For example:
# 
# ``` 
# L1 = [4,6,19,25]
# L2 = [2,4,15,29]
#          
# merge(L1, L2) = [2,4,4,6,15,19,25,29]
# ``` 

# In[42]:


def merge(L1,L2):
    # YOUR CODE HERE     
    


# After you finish, this should return True

# In[43]:


L1 = [4,6,19,25]
L2 = [2,4,15,29]
         
print(merge(L1, L2) == [2,4,4,6,15,19,25,29])

L1 = [0,39]
L2 = [6,90]

print(merge(L1, L2) == [0,6,39,90])


L1 = [0,3,14,18,39,69,68,69,73,86,91,100]
L2 = [6,7,10,24,32,65,78,80]

print(merge(L1,L2) == [0, 3, 6, 7, 10, 14, 18, 24, 32, 39, 65, 69, 68, 69, 73, 78, 80, 86, 91, 100])

L1 = [0,3,14,18,39,69,100]
L2 = [6,7,10,24,32,65,78,80,87,94,97,99]

print(merge(L1,L2) == [0, 3, 6, 7, 10, 14, 18, 24, 32, 39, 65, 69, 78, 80, 87, 94, 97, 99, 100])


# ### Question 2: Merge Sort
# 
# We will now step through how merge sort works. 
# 
# We used your `merge` function to write a recursive merge sort function. Read and understand what this function is doing. If you implemented `merge` correctly, the following should return True. 

# In[25]:


def merge_sort(unsorted):
    
    #base case
    if len(unsorted) <= 1:
        return unsorted


    # Recursive case. Divide the list in half and recursively sort them 
    left = unsorted[:len(unsorted)//2]
    right = unsorted[len(unsorted)//2:]

    left = merge_sort(left)
    right = merge_sort(right)

    #Then merge the sublists using your merge function
    return merge(left, right)


L = [4,2,6,7,5,43,2,4,567,8,76,54,32,1,3,45]
print(merge_sort(L) == sorted(L))

L = [0]
print(merge_sort(L) == sorted(L))

L = [54,323,456,78,76,5432,1,2,34,32,3,456,7,654,5,67,6,543,2,34,53]
print(merge_sort(L) == sorted(L))


# #### Question 2.1
# How many times will we call `merge_sort` with the input `L = [0]`?
Type your answer here: 

# #### Question 2.2
# How many times will we call `merge_sort` with the input `L = [4,2]`?
Type your answer here:

# #### Question 2.3
# How many times will we call `merge_sort` with the input `L = [0,23,6,4]`?
Type your answer here:

# #### Question 2.4
# 
# Let $N = len(L)$. Can you express the number of times that we will call `merge_sort` in terms of $N$?
Type your answer here:

Number of times that merge sort is called = ?
# #### Question 2.5
# With the input list `L = [0,23,6,4]`, what will `left` and `right` be in the first call to `merge_sort`?
Type your answer here:

left = 
right = 
# #### Question 2.6
# Use your answer from **2.5**. What will the result of running `merge_sort(left)` be? Write all your steps.
Type your answer here:

# #### Question 2.7
# Use your answer from **2.5**. What will the result of running `merge_sort(right)` be? Write all your steps. 
Type your answer here:

# ###  Question 3: Inversions

# _Inversion Count_ for a list indicates how far (or close) the list is from being sorted. If list is already sorted then inversion count is 0. If list is sorted in reverse order that inversion count is the maximum. 
# Formally speaking, two elements `a[i]` and `a[j]` form an inversion if `a[i] > a[j]` and `i < j`.
# 
# _Note: There are no repeating elements in the list. _
# 
# For example:
# 
# Inversion count for `[1, 2, 3, 4]` is `0`
# 
# Inversion count for `[1, 3, 4, 2]` is `2` because **3** is placed before 2,  and **4** is also placed before 2.
# 
# Inversion count for `[4, 1, 2, 3]` is `3` because **4** is placed before 1, 2, and 3.
# 
# Inversion count for `[4, 3, 1, 2]` is `5` because **4** is placed before 1, 2, 3, and **3** is placed before 1 and 2.
# 

# #### Question 3.1
# 
# Look at the code below.

# In[19]:


def slowInversions(L):
    
    ans = 0
    cnt = 0
    
    for i in range(len(L)):
        for j in range(len(L)):
            
            cnt+=1
            
            if i<j and L[i]>L[j]:
                ans+=1
                
    return ans

print(slowInversions([4, 3, 2, 1]))


# As you may have figured out, the function `slowInversions(L)` finds the inversion count for a given list `L`. However, it does that in a very inefficient way. Now, we want to understand how many operations it does. One way to find out, is to analyze how many iterations the loops do. The variable `cnt` calculates that. What would be its value at the end of the function for `L = [4, 3, 2, 1]`. Print `cnt` to confirm your answer.
Type your answer here:

For L = [4, 3, 2, 1],

cnt = ? 

# #### Question 3.2

# Now, try running `slowInversions(L)` for different lengths of `L`. What do you notice? Can you give a formula for `cnt` expressed in terms of `len(L)`?
# 
# _Note: Your formula should be of the form $cnt = len(L)^a$, where **a** is a constant. _
Type your answer here:

cnt = ?
# #### Question 3.3
# 
# Now, we will solve the Inversion count problem by using recursion.
# 
# In questions 1 and 2 , you wrote a function to _sort_ using recursion: _merge sort_. How can you use merge sort to count inversions? 
# 
# Remember that the inversion count is a measure of _how far away_ the list is from being sorted. As you sort the list, you can keep track of the number of inversions that are _fixed_ while sorting.
# 
# Modify your solution from question 1 and 2, so that it keeps track of how many inversions are happening during sorting.
# 
# _Hint: Make a variable **ans** that stores the number of inversions. Some number of inversions are happening when we place an element from the right half before the elements on the left half. How many? After you count all inversions, return a list of size 2, containing the sorted list at index 0, and **ans** at index 1. _

# In[ ]:





# #### Question 3.4
# 
# Is this solution faster than the previous one? If so, why? 
Type your (short) answer here:


# In[ ]:





# ## Optional Extra Problems
# ### Try these if you finish the other exercises early

# ### Question 4: Maximum Number
# 
# Write a function `maxNum` that takes a list of integers `L` and returns the biggest number that can be created by concatenating the integers in the list. 
# 
# _Note: Assume that all integers have the same number of digits._
# 
# For example:
# 
# `maxNum([2, 9, 3, 5]) == 9532`
# 
# `maxNum([42, 13, 66, 17, 37]) == 6642371713`
# 
# `maxNum([123, 500, 823, 433, 222, 999, 100]) == 999823500433222123100`
# 
# 

# In[48]:


def maxNum(L):
    

print(maxNum([2, 9, 3, 5]) == 9532)
print(maxNum([42, 13, 66, 17, 37]) == 6642371713)
print(maxNum([123, 500, 823, 433, 222, 999, 100]) == 999823500433222123100)


# ### Question 5: Magic
# 
# Suppose you have a list of integers - `L` and you want to create a new list `L1` which has the following property:
# $$ $$
# 
# <center> **_`L1[i]` = number of integers in L greater than `i` _** </center>
# 
# $$ $$
# 
# For example:
# 
# If `L = [5, 2, 7]`:
# 
#     L1 = [3, 3, 2, 2, 2, 1, 1] because there are *3* integers greater than 0 and 1, *2* integers greater than 2, 3, and 4, and *1* integer greater than 5 and 6.
#     
# If `L = [2, 1, 2]`:
#     
#     L1 = [3, 2] because there are *3* integers greater than 0, and *2* integers greater than 1. 
# 
#   $$  $$
# 
# Now, we want to repeat the same procedure on `L1` in order to create `L2`.
# 
# <center> **_`L2[i]` = number of integers in L1 greater than `i` _** </center>
# 
# 
# $$ $$
# For example:
# 
# If `L1 = [3, 3, 2, 2, 2, 1, 1]`:
#     
#     L2 = [7, 5, 2] because there are *7* integers greater than 0, *5* integers greater than 1, and *2* integers 
#     greater than 2.
#     
# If `L1 = [3, 2]`:
#     
#     L2 = [2, 2, 1] because there are *2* integers greater than 0, *2* integers greater than 1, and *1* integer 
#     greater than 2.
# 
# 
# $$ $$
# Write a function called `magic` that takes `L` and returns `L2`.
# 
# _Hint: You don't have to do the described procedure. _
# 

# In[ ]:





# ### Question 6: Maximum Number (Very Hard)
# 
# Write a function `maxNum` that takes a list of integers `L` and returns the biggest number that can be created by concatenating the integers in the list. **Integers can be different lengths!**
# 
# 
# 
# For example:
# 
# `maxNum([981, 98, 8]) == 989818`
# 
# `maxNum([989, 98, 8]) == 989988`
# 
# `maxNum([2, 9, 3, 5]) == 9532`
# 
# `maxNum([42, 13, 666, 17, 1337]) == 6664217133713`
# 
# `maxNum([2, 50, 9, 8, 880, 37, 42, 71, 15, 6, 18]) == 9888071650423721815`

# In[ ]: