First time here? Checkout the FAQ!
+2 votes

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?


b)S1 and S2


d) None

asked in DS by Veteran (52.5k points)   | 118 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

Related questions

0 votes
0 answers
asked in Algorithms by pC Veteran (20.2k points)   | 44 views
0 votes
2 answers
asked in Algorithms by Arnabi Boss (5.3k points)   | 52 views
0 votes
2 answers
asked in Programming by harshit agarwal (379 points)   | 71 views

Top Users Mar 2017
  1. rude

    5246 Points

  2. sh!va

    3054 Points

  3. Rahul Jain25

    2920 Points

  4. Kapil

    2732 Points

  5. Debashish Deka

    2602 Points

  6. 2018

    1574 Points

  7. Bikram

    1444 Points

  8. Vignesh Sekar

    1440 Points

  9. Akriti sood

    1424 Points

  10. Sanjay Sharma

    1128 Points

Monthly Topper: Rs. 500 gift card

21,556 questions
26,907 answers
23,278 users