Given an array A of n + m elements. It is know that the first n elements in A are sorted and the last m elements in A are unsorted. Suggest an algorithm (only pseudo code) to sort A in O (mlogm + n) worst case running time complexity. Justify.

Question

Computers and Technology

Javier Dillon

4 May, 04:27

Given an array A of n + m elements. It is know that the first n elements in A are sorted and the last m elements in A are unsorted. Suggest an algorithm (only pseudo code) to sort A in O (mlogm + n) worst case running time complexity. Justify.

+5

Answers (1)

Know the Answer?

Alicia Gamble · Answer 1

We can divide array A into two arrays B, C

B would contain the sorted n elements.

C would contain the unsorted m elements.

Now we can sort C using merge sort with worst time complexity mlogm.

When you will have array C sorted you can concatenate with B and put it back in A.