Divide & Conquer Algorithms - 2 - Merge Sort

COMP108 Lectures 2021-04-28

Method

1. Divide the sequence of $n$ numbers into two halves.
2. Recursively sort the two halves.
3. Merge the two sorted halves into a single sorted sequence.

It is easier to merge two sequences that are already sorted, compared to two non-sorted sequences.

How to Merge

To merge two sorted sequences we keep two pointers, one to each sequence.

1. Compare the two numbers pointed.
2. Copy the smaller one to the result and advance the smaller pointer.
3. Repeat steps 1. and 2.
4. When we reach the end of one sequence, simply copy the remaining number in the other sequence to the result.

Pseudo Code

For simplicity, assume $n$ is a power of 2.

• $A$ is the full array.
• $B$ is sorting array 1.
• $C$ is sorting array 2.

Algorithm Merge(B[1..p], C[1..q], A[1..(p+q)])
	i = 1, j = 1, k = 1
	while i <= p AND j <= q do
	begin
		if B[i] <= C[j] then	// B is smaller
			A[k] = B[i]
			i++
		else	// C is smaller
			A[k] = C[j]
			j++
		k++
	end
	if i == (p + 1) then	// B is empty
		copy C[j..q] to A[k..(p+q)]
	else	// C is empty
		copy B[i..p] to A[k..(p+q)]

Example

Consider the following variables:

• $B=\{10,13,51,64\}$
  • $p=4$
• $C=\{5,21,32,34\}$
  • $q=4$

The following iterations occur:

	i	j	k	A[]
Before loop.	1	1	1	Empty
End of 1st iteration.	1	2	2	5
End of 2nd iteration.	2	2	3	5, 10
End of 3rd.	3	2	4	5, 10, 13
End of 4th.	3	3	5	5, 10, 13, 21
End of 5th.	3	4	6	5, 10, 13, 21, 32
End of 6th.	3	5	7	5, 10, 13, 21, 32, 34
After if else.				5, 10, 13, 21, 32, 34, 51, 64

Time Complexity

• Each node takes $O(r)$ time when there are $r$ integers.
• Each level takes $O(n)$ time because total number of integer is $n$.
• There are $O(\log n)$ levels.

This gives an overall time complexity of:

\[O(n\log n)\]

This is faster than other algorithms that we have seen so far.