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 (51.7k points)   | 101 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)   | 43 views
0 votes
2 answers
asked in Algorithms by Arnabi Loyal (4.7k points)   | 48 views
0 votes
2 answers
asked in Programming by harshit agarwal (379 points)   | 64 views
Top Users Feb 2017
  1. Arjun

    5288 Points

  2. Bikram

    4230 Points

  3. Habibkhan

    3952 Points

  4. Aboveallplayer

    3086 Points

  5. Debashish Deka

    2378 Points

  6. sriv_shubham

    2308 Points

  7. Smriti012

    2236 Points

  8. Arnabi

    2008 Points

  9. mcjoshi

    1690 Points

  10. sh!va

    1684 Points

Monthly Topper: Rs. 500 gift card

20,860 questions
26,010 answers
22,113 users