No compare-based sorting algorithm can guarantee to use ~ 1/2 N lg N compares (in the worst case) to sort an array of N items.

True

False

Give the array that results immediately after the 7th call (and return) from merge() when top-down mergesorting the following array of size 12: 74 72 55 65 98 44 22 16 54 36 52 18

		44 55 65 72 74 98 16 22 36 54 18 52
		44 55 65 72 74 98 16 22 54 52 36 18
		44 55 65 72 74 98 16 22 54 36 52 18
		44 55 65 72 74 98 16 18 22 36 52 54

Give the array that results after applying the standard 2-way partitioning subroutine from lecture to the following array: 58 47 90 27 82 83 99 16 41 57 22 13

		16 47 13 27 22 57 41 58 99 83 82 90
		13 16 22 27 41 47 57 58 82 83 90 99
		16 47 13 22 27 57 41 58 99 83 82 90
		16 47 13 27 22 57 41 58 99 82 83 90

Give the array that results after applying the standard 2-way partitioning subroutine from lecture to the following array: B B B A B B B A A B B A

		A A B B A A B B B B B B
		A A B A B A B B B B B B
		A A A A B B B B B B B B
		A A B A B B A B B B B B

The number of compares to quicksort an array of N equal keys is ~ N.

True

False

Partitioning an array of N items uses only a constant amount of space (other than the input array).

True

False

In the best case, the number of compares to 3-way quicksort an array of N keys (not necessarily distinct) is ~ N.

True

False

Give the sequence of keys in the array that results after performing 3 successive delete-the-max operations on the following maximum-oriented binary heap of size 10: 94 88 83 87 35 67 73 23 43 30

		83 43 73 35 30 67 23
		83 73 43 30 35 67 23
		83 43 73 30 35 67 23
		83 43 73 30 35 23 67