941 views
0 votes
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?

3 Answers

0 votes
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

1 votes
1 votes
1 answer
1
0 votes
0 votes
3 answers
2
radha gogia asked Sep 16, 2015
2,629 views
To sort n randomly generated numbers. One should prefer which sorting algo ,Quick or Heap?