1,069 views
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) ?

You are given two sorted list. Now how will you merge them?

You can consider it as one doubly linked list with n elements, where first n/2 element correspond to list 1 and remaining element correspond to list 2?

Thank You @Hemant Parihar ji. I waiting for other users reply.

@Chhotu I think we can implement merge sort inplace using linked list. For merging we can do it in O(nlogn), see this: http://www.geeksforgeeks.org/merge-two-sorted-lists-place/

One change is in the sort procedure where we need to find the middle element, when using arrays we can simply find it in O(1). But in linked list it will take O(n). I think that won't affect the recursive equation. http://www.geeksforgeeks.org/merge-sort-for-linked-list/

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(n2) time. so overall complexity will become not  O(n2log2n) but O(n2) . only merging time will increase.

@Rishabh ,

@Anu

I was thinking, it could be like this

To get merge sort in doubly linked list

1)use 2 pointer , to find mid node

Say p and q pointing 2 middle node

and p->next=NULL;//to make 2nd linked list last node to be NULL

2)Now after braking the linked list, when 2 node in each list is present at last,

again by pointer exchange we do swap.

And at last it will also be done in O(nlog n)

right?

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)
by

1 comment

Thank You @VS ji. I waiting for other users reply. Please use latex for formula's for writing answer because it may confuse  for other users (like n2)