GATE CSE 1999 | Question: 1.14, ISRO2015-42

Question

If one uses straight two-way merge sort algorithm to sort the following elements in ascending order:

     $20, \ 47, \ 15, \ 8, \ 9, \ 4, \ 40, \ 30, \ 12, \ 17$

then the order of these elements after second pass of the algorithm is:

• A. $8, \ 9, \ 15, \ 20, \ 47, \ 4, \ 12, \ 17, \ 30, \ 40$

• B. $8, \ 15, \ 20, \ 47, \ 4, \ 9, \ 30, \ 40, \ 12, \ 17$

• C. $15, \ 20, \ 47, \ 4, \ 8, \ 9, \ 12, \ 30, \ 40, \ 17$

• D. $4, \ 8, \ 9, \ 15, \ 20, \ 47, \ 12, \ 17, \ 30, \ 40$

Comments

Hi Guys,

Notice the word Two-Way merge sort. It could be N-ways also. 

---

what if it is 3-way merge.

$20,47,15,8,9,4,40,30,12,17$

$(15,20,47),(4,8,9),(12,30,40),(17)$           //after 1st pass

$(4,8,9,12,15,20,30,40,47),(17)$                 //after 2nd pass

---

is k way merging different than merging k sorted arrays??

---

whats the correct way to make initial groups to sort?
k way means start from beginning and make set of every 3 elements?

---

what mean by second-pass of the algorithm ?

---

https://stackoverflow.com/questions/56696667/2-way-merge-sort-and-merge-sort

Another name for an iterative 2-way merge sort is bottom up merge sort, while another name for recursive merge sort is top down merge sort. 

---

Is this the reason why we are not dividing the array from the center and just making the groups of two adjacent elements?

---

General tip:

The n-way merge sort is the iterative version and the usual merge sort is the recursive version.

I got easily confused with the two versions of merge sort in the beginning.

---

An example to understand the difference between $2$ – way MergeSort (Iterative version) and MergeSort (Recursive version) has been explained by satbir in the below question.

https://gateoverflow.in/89083/gate1989-9

---

For 1st pass we compare two two groups of elements at a time , for second pass we compare four four groups of elements at a time

Answer 1

The answer is B.

Comments

Here they are asking about the result after 2nd pass, since pass will not give a useful meaning in recursive top-down approach, we have to use bottom-up approach (also because qns mentions "2-way merge", 2-way merge actually works in bottom-up manner). To know the working of bottom up approach and difference between top-down and bottom up approach of merge sort: http://www.mathcs.emory.edu/~cheung/Courses/171/Syllabus/7-Sort/merge-sort5.html
https://stackoverflow.com/questions/17417887/where-is-bottom-up-merge-sort-useful

---

.

---

nice explaination

Answer 2

Two Way MergeSort is Different from Merge Sort

Two way MergeSort is Iterative Procedure while MergeSort is Recursive Procedure

Maybe this video help understanding 2-way(or M-way) merging better...

https://www.youtube.com/watch?v=6pV2IF0fgKY

Answer 3

A/c to me its answer is option (b).

8, 15, 20, 47, 4, 9, 30, 40, 12, 17 b/c it uses two-way merge sort.

Take question as A: [20] [47] [15] [8] [9] [4] [40] [30] [12] [17]

After pass 1: [20,47] [15,8] [4,9] [30,40] [12,17]

After pass 2: [8,15,20,47] [4,9,30,40] [12,17]

After pass 3: [4,8,9,15,20,30,40,47] [12,17]

After pass 4: [4,8,9,12,15,17,20,30,40,47]