The Gateway to Computer Science Excellence
0 votes
369 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.3k points) | 369 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,647 questions
56,493 answers
195,481 comments
100,789 users