retagged by
740 views
3 votes
3 votes
Merge sort using linked list is better than array in terms of space complexity

true or not with explanation :)
retagged by

1 Answer

Best answer
1 votes
1 votes
The mergesort algorithm is recursive, so it requires O(log n) stack space, for both the array and linked list cases. But the array case also allocates an additional O(n) space, it requires O(n) space because unlike linked list we cannot put an element in between 2 adjacent elements in an array due to which it requires O(n) extra space as compared to linked list which require O(logn) extra space.  In linked list, we can insert items in the middle in O(1) extra space and O(1) time. It's better to implement merge sort with linked list than with implementing it with array.
selected by

Related questions

0 votes
0 votes
0 answers
2
Ujjal Das asked Mar 17
83 views
Calculate the minimum and maximum number of element comparisons involved in 2 way merge sort assuming n is power of 2.
0 votes
0 votes
0 answers
4
Nandkishor3939 asked Jan 21, 2019
679 views
What is the extra memory needed for merge sort:1] In case of Iterative merge sort.(DS:Array)2]In case of Recursive merge sort.(DS:Array)3] In case of Iterative merge sort...