Merge Sort

Question 1

The merge sort algorithm closely follows the divide-and-conquer paradigm.
It operates as follows.

Divide: Divide the n -element sequence to be sorted into two
subsequences of n/2 elements each.

Conquer: Sort the two subsequences recursively using merge sort.

Combine: Merge the two sorted subsequences to produce the sorted
answer.

Question 2

How many sub-sequences will an n-element sequence be divided into?

Answer 2

2

Question 3

How many elements are there in each sub-sequence?

Answer 3

n/2 elements (so, half the elements)

Question 4

What sized sub-sequence is small enough to be solved in a straightforward manner?

Answer 4

1

Question 5

The MERGE (A, p, q, r) procedure takes four parameters, what does each of them stand for?

Answer 5

A = Array
p,q,r = indices

p <= q < r

Question 6

What is ꚙ? Why do we need it in the MERGE procedure?

Answer 6

This is the sentinel which is placed at the bottom of each subarray.
It simplifies our code by signaling that we have hit the end of the ‘pack’ and means that we don’t have to check whether or not our subarrays are empty with every iteration.

Question 7

What is the most important operation of the merge sort algorithm?

Answer 7

The merging of two sorted sequences in the “combine” step.

Question 8

Merge Procedure - Time

What does the merge procedure (the merge part of the algorithm) take where n = r - p + 1 (as the total number of elements being merged)?

Answer 8

theta(n)

Question 9

Time Complexity 1

N.B log base 2 is considered cutting in half.
See YouTube https://www.youtube.com/watch?v=M4ubFru2O80
0:53 - 1:36