205 views

Consider the following statement:
S1: Merge sort on linked list take O(n log n) time to sort input of length n.
S2: Merge sort on linked list give better space complexity then on array.
S3: Inplace merge sort on array will take O(n2) time.
Which of the following is correct?

a)S1

b)S1 and S2

c)S1,S2,S3

d) None

asked in DS | 205 views
I think only S1 is correct.

i)Merge sort on list takes O(nlogn)

ii)Merge sort on linked list takes more space than array because list contains pointer(next,prev) it takes extra space.

iii)In place meger sort also takes only O(nlogn).

s3: in place mergesort on array .will take O(n2) ( true)

ryt .??

But according to this source in place merge sort in worst case it will take O(n^2)...can u pls clarify

no,2-way merge sort is inplace and its complexity is O(nlogn)
yes, Ans given C)
How s2 will be correct?
@srestha

Merege sort on linked list takes more space complexity than array.S2 is wrong
So which option is correct A or D
i think A is correct.
@Srestha and @santhos i think option d) is correct .??
Could you explain

How S1 will be correct?

How S1 and S2 are not correct ?

+1 vote
S3 is correct

In above question, there is no option given related to only s3 .

That's why option d is correct .

.
answered by Active (1.3k points) 1 2 16
@ 2-way mege sort is inplace sorting algorithm

and its worst case time complexity is O(nlogn).

we can implement Merge sort using linked lists in O(nlogn) time

1
+1 vote
2