in Algorithms
485 views
0 votes
0 votes
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.(DS:Linked List)

4]In case of Recursive merge sort.(DS:Linked List)
in Algorithms
485 views

2 Comments

Case :1 Only extra array of size n will be needed.

Case 2: Extra array + Stack space

Case 3: I think we will not need any extra space for rersult as we can just change the links.

Case 4. only stack space will be extra.
3
3
I think, even in array variant of iterative merge sort we can perform in-place sorting. Hence, O(1) for case 1 too.
0
0

Please log in or register to answer this question.