1. Recall the insertion sort algorithm (contiguous version) as discussed in this chapter. Assume the following list of keys: 18 8 11 9 15 20 32 61 22 48 75 83 35 3 Exactly how many key comparisons are...

1. Recall the insertion sort algorithm (contiguous version) as discussed in this chapter. Assume the following list of keys:

Exactly how many key comparisons are executed to sort this list using the insertion sort algorithm?

13. Both the merge sort and quick sort algorithms sort a list by partitioning it. Explain how the merge sort algorithm differs from the quick sort algorithm in partitioning the list.

2. Assume the following list of keys:

This list is to be sorted using the quick sort algorithm as discussed in this chapter. Use pivot as the middle element of the list.

a. Give the resulting list after one call to the partition procedure.

b. Give the resulting list after two calls to the partition procedure.