GATE Overflow | Mock GATE | Test 1 | Question: 62

Question

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

• A. $\text{Insertion sort, } O(\log ^2 n)$
• B. $\text{Merge sort, } \Theta (( \log n) \log (\log n ))$
• C. $\text{Heap sort, } \Theta ( \log ^2)(\log n ))$
• D. $\text{Quick sort, } O ( \log 2)(\log n ))$

Comments

What are the other complexities for the corresponding algorithms in options?

---

B is right answer

---

In insertion sort, if we find at index i, we have a greater element, we shift it to (i-1). Singly Linked List would be a nightmare for this. Each time we'll have to traverse all the way fro head to (i-1).

Heap sort wants random access for rearrangements (heapify). In a Linked List, there's no such thing as random access.

Even quicksort requires random access.

 

Merge sort is done with linear access. First we'll compare both the first elements of the two-sub lists... we all know how it goes.

Merge sort is suitable here.

Answer 1

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)$.

Comments

What's wrong in option A?

We can implement insertion sort on SLL in O(n^2) time for n element list.

Just difference is we will start from head to find correct position of element.

---

@tp21 $log^2n > logn ^{*} loglogn$