recategorized by
1,548 views
6 votes
6 votes

Which of the following sorting algorithms performs efficiently to sort a singly linked list containing $\log n$ nodes and the corresponding time complexity is?

  1. $\text{Insertion sort, } O(\log ^2 n)$
  2. $\text{Merge sort, } \Theta (( \log n) \log (\log n ))$
  3. $\text{Heap sort, } \Theta ( \log ^2)(\log n ))$
  4. $\text{Quick sort, } O ( \log 2)(\log n ))$
recategorized by

1 Answer

Best answer
4 votes
4 votes

Merge sort is the best known algorithm to sort a linked list in $Θ(nlogn)$ time, and this is even in-place sorting unlike array sorting by merge sort which is not in-place.

There are logn elements in the linked list, hence the overall T.C will be $Θ(logn*loglogn)$.

selected by
Answer:

Related questions

8 votes
8 votes
2 answers
3
Ruturaj Mohanty asked Dec 27, 2018
1,270 views
For a given $m$-ary tree, the relationship between leaf nodes and internal nodes is represented by the graph given below. What is the value of $'m'$? Take necessary appro...