Hi community, I need to solve the following problem: Consider the following algo

Question

Hi community, I need to solve the following problem:


Consider the following algorithm to sort N elements: Place each element in its own list. Then repeat the
following step N - 1 times: Choose two lists, and merge them. Note that at any point, the merge reduces the
number of lists by one, but maintains all lists in sorted order. Thus at the end, what remains is a single sorted
list of N elements.
Assume an efficient implementation of lists, stacks, and queues. Assume that merging two lists will always take
time linear in the size of the resulting list.
(a) Suppose the initial N lists are placed on a stack. At any point, the first two lists are chosen to merge,
and the result is placed at the top of the stack. What is the running time of the sorting algorithm?
(b) Suppose the initial N lists are placed on a queue. At any point, the first two lists are chosen to merge,
and the result is placed at the back of the queue. What is the running time of the sorting algorithm?

Explanation / Answer

(a) O(n^2) (b) O(nlogn)

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

---

---

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