retagged by
429 views
0 votes
0 votes
can anyone explain in detail why and how is merge sort optimal for linked list?
retagged by

1 Answer

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

Related questions

4 votes
4 votes
1 answer
1
Shivi rao asked Oct 10, 2017
1,513 views
True or FalseMerge sort on Linked list takes O(nlogn)
1 votes
1 votes
1 answer
2
patilnivedita asked Jun 25, 2017
549 views
Assume 5 buffer pages are available to sort a file of 105 pages. The cost of sorting using m-way merge sort is
3 votes
3 votes
3 answers
3
srestha asked Jan 4, 2017
3,719 views
Consider the following statement:S1: Merge sort on linked list take O(n log n) time to sort input of length n.S2: Merge sort on linked list give better space complexity t...
1 votes
1 votes
1 answer
4
kumar.dilip asked Jan 19, 2019
666 views
The average no. of comparisons performed by the merge sort algorithm, in merging 2 sorted lists of length 2 is___________.Ans: $\frac{8}{3}$