Log In
0 votes
If we talk about that since since we cant access any random element in a linked list for that reason quick sort cant be used for linked lists ,then in merge sort also we need  a middle element for splitting so then how do we actually use merge sort then , also even if chosing the pivot takes O(n) time then it will only add up with the time taken for partition as such no issue in it then why can't we use quicksort for implementing linked lists?
in Algorithms 572 views

3 Answers

0 votes
We prefer insertion sort over selection sort because in selection sort it takes atleast n comparisons for each element for already sorted list..but in insertion sort no such comparisons are made....and merge sort have o(1) space complexity in linked lists..
0 votes
0 votes
There is no issue in implementing quick sort with link list but it does not enhance performance of quick sort while in case of merge sort the time complexity being the same it improves space complexity and through link list it can be done in-place (without using extra space)

Related questions

0 votes
3 answers
To sort n randomly generated numbers. One should prefer which sorting algo ,Quick or Heap?
asked Sep 17, 2015 in Algorithms radha gogia 1.3k views
0 votes
2 answers
Given an array of distinct integers A[1, 2,…n]. Find the tightest upper bound to check the existence of any index i for which A[i]= i. (a) O (1) (b) O (log n) (c) O (n) (d) None of these Solution: Option (c)
asked Nov 10, 2018 in Algorithms Mak Indus 49 views