GATE CSE
First time here? Checkout the FAQ!
x
+2 votes
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 by Veteran (65.4k points) 35 224 638 | 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

http://penguin.ewu.edu/cscd300/Topic/AdvSorting/MergeSorts/InPlace.html
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?
see the link @Deepak

How S1 and S2 are not correct ?

 

1 Answer

+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

Related questions

+3 votes
1 answer
1
0 votes
0 answers
3
asked in Algorithms by pC Veteran (23k points) 50 219 362 | 70 views


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
Top Users Oct 2017
  1. Arjun

    23706 Points

  2. Bikram

    17298 Points

  3. Habibkhan

    9336 Points

  4. srestha

    6566 Points

  5. Debashish Deka

    5478 Points

  6. jothee

    5188 Points

  7. Sachin Mittal 1

    4910 Points

  8. joshi_nitish

    4514 Points

  9. manu00x

    4158 Points

  10. sushmita

    4098 Points


Recent Badges

Verified Human Terminator
Verified Human maheshtheng
Nice Answer Ahwan
Renewal Ahwan
Notable Question pranab ray
Notable Question Tuhin Dutta
Great Question jothee
Ancestor santhoshdevulapally
Nice Question Pradip Nichite
Famous Question smartmeet
27,447 questions
35,307 answers
84,718 comments
33,549 users