In-place Merge Sort via Doubly linked list in place of Array

Question

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.

Comments

@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(n²) time. so overall complexity will become not  O(n²log₂n) but O(n²) . 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

make temp1 = p->next;//to make head pointer of 2nd linked list

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?

Answer 1

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)

Comments

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)