Merge sort

Question

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)

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.

---

I think, even in array variant of iterative merge sort we can perform in-place sorting. Hence, O(1) for case 1 too.