The Gateway to Computer Science Excellence
0 votes
54 views
can anyone explain in detail why and how is merge sort optimal for linked list?
in DS by Active (5.1k points)
retagged by | 54 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 (343 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,492 answers
195,439 comments
100,707 users