search
Log In
5 votes
710 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
retagged by
710 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)
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

8 votes
2 answers
1
2.4k 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 getting wrong plz help...
asked Nov 7, 2016 in Algorithms vineet.ildm 2.4k views
0 votes
3 answers
2
1.1k views
First read it properly. I am not asking a specific question about space complexity. Question: What is worst case space complexity of quick sort? Everywhere it is showing O(logn). My understanding about it: I know that Quick sort algorithm doesn't request extra space except for ... if partition is being done by ratio 1:n-1 which is worst case, wouldn't it be requesting for O(n) stack records?
asked Apr 21, 2018 in DS Akash Kumar Roy 1.1k views
3 votes
1 answer
3
751 views
Consider the following algorithm to build a balanced search tree from a sorted sequence. * Make the mid-point of the sequence the root of the tree * Recursively construct balanced search trees from elements to the left and right of the midpoint and make these the left and right subtrees of the ... a sorted array? 1- O(n) 2- O(n log n) 3- O(n2) 4- Depends on the contents of the original sequence
asked Aug 23, 2016 in Algorithms dd 751 views
0 votes
1 answer
4
594 views
Insertion of a node into a doubly linked list requires how many changes to various Next and Previous Pointer? A. No Change B. 1 Next , 1 Previous C. 2 Next , 2 Previous D. 3 Next , 3 Previous
asked Jun 28, 2017 in DS Arnab Bhadra 594 views
...