The Gateway to Computer Science Excellence
+5 votes
316 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) ?

Please share your valuable opinion. It will be great help.
in Algorithms by Boss (13.7k points)
retagged by | 316 views
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?
0

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

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

1 Answer

+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)
by Boss (10.8k points)
+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)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,312 answers
198,343 comments
105,036 users