• retagged by
592 views
0 0 votes
CAn anyone explian about 2-way merge sort ?

(You can take example from GATE1999-1.14, ISRO2015-42)

1 Answer

Best answer
4 4 votes
In regular merge sort array is recursively get divide until single element is obtained. From there we pick the each element and sort them(which is kinda obvious single element is already sorted). Then we obtain two elements arraya and compare and merge them.

 

2-way merge sort we take 2 elements at a time instead of 1 from the point we have divided the array to singleton element.

 

8-7-6-5-4-3-2-1

{8,7}-{6,5}-{4,3}-{2,1}// see pick two elements at a time now sort them

{7,8}-{5,6}-{3,4}-{1,2} // again pick two sorted elements and merge them then sort

{7,8,5,6}-{3,4,1,2}// sort them

{5,6,7,8}-{1,2,3,4} // again we obtain sorted elements now again merge

{5,6,7,8,1,2,3,4} // now sort them again

{1,2,3,4,5,6,7,8} // sorted using 2-way merge sort.

 

Hope you get the difference.

It is just same after second​ step of regular merge sort.
• selected by
Position:
Show:

Related questions

1 1 vote
1 1 answer
1.4k
1.4k views
kumar.dilip asked Jan 19, 2019
1,418 views
The average no. of comparisons performed by the merge sort algorithm, in merging 2 sorted lists of length 2 is___________.Ans: $\frac{8}{3}$
0 0 votes
3 3 answers
1.7k
1.7k views
aditi19 asked Oct 6, 2018
1,708 views
what is the recurrence relation for merge sort?
1 1 vote
3 3 answers
2.2k
2.2k views
Shubhanshu asked Jun 6, 2017
2,208 views
You are asked to sort 15 randomly generated numbers. One should prefer—(a) Bubble sort (b) Quick sort (c) Merge sort (d) Heap sortI think the answer should be c or d crct...
1 1 vote
1 1 answer
154
154 views
GO Classes asked Aug 10
154 views
Mergesort recursively sorts the two halves of an array.After both recursive calls have finished, but before the merge operation, which statement must be true?The complete...