Question

Merge sort using linked list is better than array in terms of space complexity

true or not with explanation :)

Comments

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, which dominates the O(log n) space required for the stack. So the array version is O(n), and the linked list version is O(log n)

Answer 1

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.