2. Short programming assignment. Implement a bottom-up mergesort that first sort

Question

2. Short programming assignment. Implement a bottom-up mergesort that first sorts blocks of M elements using insertion sort. Test your program with large sets of random data and determine what value of M works best.

3. The following refer to linked list mergesort Explain why mergesort is more suitable for linked lists than other sorting methods.

a. Explain why mergesort is more suitable for linked lists than other

b. Consider a file that is “mostly sorted.” Explain how the principles of linked-list merge could be used to quickly produce a sorted file.

4. For each of the following priority-queue operations, give a implementation in which the operation is optimal (that is, O(1)), and an implementation in which the operation is worst-case (that is, O(N)). Briefly explain how the operation is performed under the implementation you have chosen.

a. Insert

b. Remove maximum

c. Change priority

d. Join

Explanation / Answer

Merge sort is a sorting algorithm that uses the idea of divide
and conquers. This algorithm divides the array into two halves, sorts them
separately and then merges them. This procedure is recursive, with the base
criterion-the number of elements in the array is not more than 1. Suppose variable
low and high represents the index of the first and last element of the array
respectively, the merge sort can be defined recursively as
If(low<high) then
Divide the list into two halves
Mergesort the left half
Mergesort the right half
Mergesort the two sorted halves into one sorted list
Endif.

Time complexity of merge sort is O(N log2 N) Time complexity of heap sort is O(nlog2n)

n Insertion Sort bulk move (Bn) Naïve Insertion Sort (Sn) 1,024 0.0039 0.013 2,048 0.0153 0.0516 4,096 0.0612 0.2047 8,192 0.2473 0.816 16,384 0.9913 3.2575 32,768 3.9549 13.065 65,536 15.872 52.291 131,072 68.401 209.29

Related Questions

Navigate

• Browse (All)
• Browse 2
• Subjects

---

---

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