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?

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?

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.

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

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))
```

How many times will we call `merge_sort`

with the input `L = [0]`

?

How many times will we call `merge_sort`

with the input `L = [4,2]`

?

How many times will we call `merge_sort`

with the input `L = [0,23,6,4]`

?

Let $N = len(L)$. Can you express the number of times that we will call `merge_sort`

in terms of $N$?

With the input list `L = [0,23,6,4]`

, what will `left`

and `right`

be in the first call to `merge_sort`

?

Use your answer from **2.5**. What will the result of running `merge_sort(left)`

be? Write all your steps.

Use your answer from **2.5**. What will the result of running `merge_sort(right)`

be? Write all your steps.

*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.

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

`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.

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. *

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. *

Is this solution faster than the previous one? If so, why?

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)
```

Suppose you have a list of integers - `L`

and you want to create a new list `L1`

which has the following property:
$$ $$

$$ $$

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`

.

$$ $$ 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. *

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`