1. Both the merge sort and quick sort algorithms sort a list by partitioning it.

Question

1. 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: 36, 55, 89, 95, 65, 75, 13, 62, 86, 9, 23, 74, 2, 100, 98 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 function partition.

b. What is the size of the list that the function partition partitioned?

c. What are the sizes of the two sublists created by the function partition?

Explanation / Answer

In Quicksort, the actual sorting step is done during the splitting (move elements to the left or right half, depending on the comparison with the pivot element) and there is no merging step to get back up the tree (as observed from the data point of view; your implementation may of course have stack unwinding), while in Mergesort, the sorting is done on the way up

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.