Merge Sort Exercises

mergesortA.png

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

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

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

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.

Question 3.4

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

Type your (short) answer here:

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: $$ $$

**_`L1[i]` = number of integers in L greater than `i` _**

$$ $$

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.

**_`L2[i]` = number of integers in L1 greater than `i` _**

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

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