The Gateway to Computer Science Excellence
+3 votes
Which of the following is worst choice to sort a linked list?

a)Merge Sort

b) Quick Sort

c) heap sort

d) Insertion sort
in DS by | 429 views
I think heap sort is completely impossible for linked list.
explain a bit , why do  u think impossible?

2 Answers

0 votes

Heap sort is inefficient on linkedlist

why because

it completely depends on the random access facility of the array, but linked list does not support random access.

ref  :

0 votes

Answer is Heap sort as it most dependent on random access which is costly in case on Linked List.

Detailed Explanation:

Merge Sort for Linked Lists:

Merge sort is often preferred for sorting a linked list. The slow random-access performance of a linked list makes some other algorithms (such as quicksort) perform poorly, and others (such as heapsort) completely impossible.

1) If the head is NULL or there is only one element in the Linked List 
    then return.
2) Else divide the linked list into two halves.  
      FrontBackSplit(head, &a, &b); /* a and b are two halves */
3) Sort the two halves a and b.
4) Merge the sorted a and b (using SortedMerge() discussed here) 
   and update the head pointer using headRef.
     *headRef = SortedMerge(a, b);

Time Complexity: O(n Log n)

Quick Sort on Linked List:

Partition Algorithm
1. Take rightmost element as the pivot
Traverse through the list
    a. If the node has value greater than pivot, we will move it after tail

  b. else, keep it in same position

QuickSort Algorithm
1. Call Partition(), which places pivot at right position and returns the pivot
2.  Find the tail node of the left sublist ie, left side of the pivot and recur for left list

3.  Now, recur for right list

Below is simple insertion sort algorithm for linked list.

1) Create an empty sorted (or result) list
2) Traverse the given list, do following for every node.
......a) Insert current node in sorted way in sorted or result list.
3) Change head of given linked list to head of sorted (or result) list

Heap Sort on Linked List

Heapsort is a good sorting algorithm because it's O(n log n) and it's in-place. However, when you have a linked list heapsort is no longer O(n log n) because it relies on random access to the array, which you do not have in a linked list. So you either lose your in-place attribute (by needing to define a tree-like structure is O(n) space). Or you will need to do without them, but remember that a linked list is O(n) for member lookup. Which brings the runtime complexity to something like O(n^2 log n) which is worse than bubblesort.




Heap sort can be applied when we have a heap data structure. And a heap is a non linear data structure, while a linked list is a linear data structure. Thus, the very basic underlying data structure prevents heap sort being used on a linked list.

Heap sort can be applied on array as the heap data structure can be easily implemented using indexing.Also, "structures"(nodes) can be used to construct heap and heap sort can be applied on that just like we do for arrays.

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
52,315 questions
60,427 answers
95,237 users