GATE CSE
First time here? Checkout the FAQ!
x
+2 votes
83 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 (49.8k points)   | 83 views
@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)  
@ 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
Top Users Jan 2017
  1. Debashish Deka

    9614 Points

  2. sudsho

    5554 Points

  3. Habibkhan

    4878 Points

  4. Bikram

    4774 Points

  5. Vijay Thakur

    4498 Points

  6. Arjun

    4408 Points

  7. saurabh rai

    4236 Points

  8. Sushant Gokhale

    4112 Points

  9. Kapil

    3830 Points

  10. santhoshdevulapally

    3808 Points

Monthly Topper: Rs. 500 gift card

19,371 questions
24,203 answers
53,828 comments
20,368 users