2.1 Merge Sort

Question 1

What is Divide and Conquer?

Answer 1

Divide: an instance into smaller instances of the same problem
Conquer: by recursively solving the sub-instances until we can solve directly
Combine: the partial solutions to the solution for the original instance

Question 2

What is recursion

Answer 2

A function that calls itself

Question 3

When combining left and right part of array, what are the formulas for n1 and n2? (the lengths of the two arrays)

Answer 3

n1 = m - L + 1
n2 = r - m

Question 4

What is a sentinel

Answer 4

Usually infinity, used to compare to the biggest number in the array. So the biggest number in the array is compared and then goes at the end.

Question 5

How many comparisons does Merge make?

Answer 5

r - L + 1 (n)

Question 6

What techniques are used to prove correctness of MergeSort?

Answer 6

Using proof by induction

Question 7

Can merge sort be done in situ (using only the array you were given and no extra space)

Answer 7

No

Question 8

Is MergeSort stable? If there are 2 1’s in the array will the first 1 always stay before the second 1?

Answer 8

Yes

Question 9

Pros and Cons of merge sort

Answer 9

Pro:
Divide and Conquer
Good ‘worst case’ running time O(nlog(n))

Con:
Not in situ (needs an extra n space)