retagged by
1,326 views
5 votes
5 votes
In general merge sort is not considered in-place sorting technique. Because an auxiliary array is used. If we will try to do it in-place in array data structure then our merge procedure will take O($n^2$) time. so overall complexity will become O($n^2\log_2 n $).

But can not we do it In-place in O($n \log n $), using a doubly linked list in place of Array (for storing and merging data) ?

Please share your valuable opinion. It will be great help.
retagged by

1 Answer

2 votes
2 votes
First of all inplace merge :

T(n)=2T(n/2) + O(n2)

Using master theorem f(n) = Big Omega(n)

T(n)=O(n2)

Yes,if we use linked lists for merge sort ,

1)finding mid =O(n)

2)solving recursively 2T(n/2)

3)Inplace merge using Linked lists =O(n)

T(n)=2T(n/2) + O(n)

=O(nlgn)

Related questions

9 votes
9 votes
2 answers
1
vineet.ildm asked Nov 7, 2016
5,807 views
Why space complexity of heapsort is O(1)....and why not O(logn)..because of space required by recursion calls which is equivalent to height of the tree...where am i getti...
0 votes
0 votes
1 answer
3
Arnab Bhadra asked Jun 28, 2017
3,311 views
Insertion of a node into a doubly linked list requires how many changes to various Next and Previous Pointer?A. No ChangeB. 1 Next , 1 PreviousC. 2 Next , 2 PreviousD. 3 ...