Question 7.

11 Show how heapsort processes the input:

142, 543, 123, 65, 453, 879, 572, 434, 111, 242, 811, 102.

Solution.
Step 1 Build the heap.
1.1 Place all the data into a complete binary tree in the order given. You should
get:

142

543 123

65 453 879 572

434 111 242 811 102

Fig. 1. After Step 1.1.

1.2 Now turn it in to a maximum heap (i.e. that is the root is the largest element
of each subtree). You should get:

879

811 572

434 543 123 142

65 111 242 453 102

Fig. 2. After Step 1.2.

Step 2. Remove the maximum element from the heap 12 times and store in
an array in reverse order (i.e. place the first element removed in position 12).
The heap order property must be maintained after each deletion. After the first
deletion the heap should look like this:

811

543 572

434 453 123 142

65 111 242 102

879

Fig. 3. After the first deletion.

After the fifth deletion the heap should look like this:

434

242 142

111 65 123 102

453 543 572 811 879

Fig. 4. After the fifth deletion.

Continue this process until all no elements remain in the heap.

Note. The use an extra array to store the result can be avoided by placing
deleted elements at the end of the heap and marking them as not being in the
heap.
Question 7.12 What is the running time of heapsort for presorted input?

Solution. O(N log N ).

Question 7.19 Sort 3, 1, 4, 1, 5, 9, 6, 5, 3, 5 using median-of-three partitioning

and a cut-off of 3.

Solution. “Median-of-three” refers to the strategy used to choose the pivot

element. The cut-off is the array size at which insertion sort is used in place of
quicksort. The reason for this is that insertion sort beats insertion sort if the
number of elements to be sorted is small.

1st 6th 11th

3 1 41 5 9 2 6 5 3 5
Initial Set

3 1 41 5 5 2 6 5 3 9
The first, middle, and last element are sorted

3 1 41 5 3 2 6 5 5 9
The median is "hidden" in the second last position.

3 1 41 5 3 2 5 5 6 9
Partition the remainder of the elements and swap the pivot back.

Fig. 5. Following the initial partitioning.

There are only two elements in the RHS partition. An insertion sort subrou-
tine is called to sort these two elements. Quicksort is recursively applied to the
elements in the LHS of the pivot.
 1st 4th 8th
3 1 4 1 5 3 2 5
Initial Set

1 1 4 3 5 3 2 5
The first, middle, and last element are sorted

1 1 4 2 5 3 3 5
The median is "hidden" in the second last position.

1 1 3 2 3 4 5 5
Partition the remainder of the elements and swap the pivot back.

Fig. 6. Following the second partitioning.

Again the number of elements to the RHS of the pivot is ≤ 3 and thus are
sorted with a call to an insertion sort subroutine.

1st 2nd 4th

1 1 3 2
Initial Set

1 1 3 2
The first, middle, and last element are sorted

1 3 1 2
The median is "hidden" in the second last position.

1 1 3 2
Partition the remainder of the elements and swap the pivot back.

Fig. 7. Following the third partitioning.

Now the number of elements of both the LHS and the RHS is less than equal
to the cut-off of 3 and so is sorted using an insertion sort subroutine.
Question 7.20 Using the quicksort implementation of this chapter, determine
the running time of quicksort for:

(a) Sorted Input;

(b) Reverse Ordered Input;
(c) Random Input.

Solution.
(a) O(N log N ) . This is because the size of the problem is exactly halved at
each step, at a cost that is linear to the current size.
(b) O(N log N ) . For the same reasons as in (a).
(c) This question requires you to do an average case analysis of quicksort. This
is done in the notes. The answer is O(N log N ).

Question 7.32 Suppose you are given a sorted list of n elements followed by
f (n) randomly ordered elements. How would you sort the entire list if
1. f (n) = O(1)
2. f (n) = O(log
√ n)
3. f (n) = O( n)
4. How large can f (n) be for the entire list to be still sortable in O(n) time?
Solution. Looking at each case:
1. If there are just a handful of unsorted elements – a constant number, say, k
– at the end then we could just run k iterations of the inner loop of insertion
sort. This will be a running time of O(k · n). Alternatively, we could sort
these k elements separately and then perform a merge: a constant number
of elements can be sorted in a constant amount of time and the merge takes
n + k writes into a new array and another n + k to copy back to the original.
2. If there are O(log n) extras then the insertion-sort approach will require
O(n log n) time. If we independently sort them and then merge the two
pieces together we will take time: O(log n·log log n) to sort the extra elements
and then, as in the previous part, merge the two pieces in time n + log n
(merge/write)√and n + log n to copy back, which is in√all O(n). √ √
3. If there are
√ O( N ) extras then we can sort these in O( n log n) = O( n log n)
since log n = log n − log 2 = O(log n). Note that this sorting is still o(n)
(dominated by a multiple of n). √
Merging can be done in two steps of, respectively, n + n (merges/writes)
and the same to copy back. This is still O(n).
4. If f (n) = O(n/ log n) then sorting can be done in
n n
n
O( log ) = O( (log n − log log n)) = O(n) − o(n)
log n log n log n
Question 7.32 Prove that any algorithm that finds an element x in a sorted
list of n elements requires Ω(log n) comparisons.
Solution. This can be argued by the “20 questions”-style of argument that we
used for lower bounds on sorting. Since we could imagine an input that would
require us reporting any of the n different array positions we have to have a
separate outcome (leaf node) corresponding to each of these possibilities.
In order for a binary tree (since only 2-way comparisons are allowed) to have
n leaves we require a depth of at least dlog ne = Ω(log n).

N √
Question 7.34 Using Stirling’s Formula, N ! ≈ Ne 2πN , give a precise
estimation for log(N !).
Solution.
 N
N √
log(N !) ≈ log 2πN
e
 N
N √
≈ log + log 2πN
e
√
 N
N
≈ log N
+ log 2πN
e
√
≈ log N − log eN + log 2πN
N

≈ log N N − log eN
≈ N log N − N log e
Question 2. Row (column) sorting an array of numbers means taking each row
(column) and sorting numbers in that row. Given an m × n array of numbers
(m rows of n numbers), if the array is row-sorted and then column-sorted, is the
array still row-sorted?

Solution. Yes. The proof is by contradiction.

Assume that a pair aij , aij+1 exists such that aij > aij+1 (such a pair exists
if and only if the matrix is not row sorted). Because the matrix is column sorted
this implies that every element in the set {aij , ai+1j , ..., amj } is greater than
every element in the set {a1j+1 , a2j+1 , ..., aij+1 }. Now,

|{aij , ai+1j , ..., amj }| = m − i + 1

Thus at most i − 1 elements from column j are less than the elements in the
set {a1j+1 , a2j+1 , ..., aij+1 }. But,

|{a1j+1 , a2j+1 , ..., aij+1 }| = i

Therefore no matter what the permutation of the elements in column j at
least one element from the set {a1j+1 , a2j+1 , ..., aij+1 } will be in the same row as
an element in column j that is greater than it. But column sorting only changed
the permutations of the elements in the columns. Therefore the matrix must not
have been row-sorted.