The Gateway to Computer Science Excellence
0 votes
75 views
can anyone explain in detail why and how is merge sort optimal for linked list?
in DS by
retagged by | 75 views
0
Because it is in place in case of linked list, and time required is same as for arrays.
+2
Two sorted linked list can be merged into one sorted link list by just exchanging pointers that would require no extra space.

1 Answer

0 votes
In a linked list since random access is a slow process or we can say not so feasible, quick sort is very slow(due to lot of random access) and heap sort is impossible.Thus we go with merge sort as in this we only have to keep track of two pointers and no extra space is needed during the merge operation as insertion in linked list is O(1) .O(nlogn)
by
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,314 questions
60,435 answers
201,774 comments
95,251 users