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?

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.

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.

0

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?

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?

1

@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/

1

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 not O(n^{2}log_{2}n) but O(n^{2}) . only merging time will increase.

0

@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?

@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?

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)

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)

1

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)