The Gateway to Computer Science Excellence
0 votes
370 views
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 by Loyal (6.4k points) | 370 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..
by (59 points)
0 votes
by Active (2.1k points)
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)
by Active (1.7k points)
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
50,737 questions
57,284 answers
198,183 comments
104,863 users