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

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

Answer 1

The answer is B.

Comments

very nice way of answering :)

Also, these kind of walking through algorithm questions are quite common in GATE. Those who just studies formula won't be able to answer these. And these questions are the ones that separate GATE toppers from others.

---

How the 2 way merge is different from the merge sort procedure

---

https://en.m.wikipedia.org/wiki/K-Way_Merge_Algorithms

 

 

 

Visit this

---

The answer uses a bottom up approach.

What if we use a top down approach instead?

(Solving recursively left side first )

After Pass 1:

|20 47| 15 8 9 4 40 30 12 17

After Pass 2:

|20 47|  |8 15| 9 4 40 30 12 17

 

DOUBT!

---

Merge sort is by default bottom-up. Anywhere have you seen top-down solution?

---

sir, not seen the solution to this particular question but, asking if this is possible for this question.

http://www.geeksforgeeks.org/merge-sort/  - here they are using top-down approach (see the  numbering of operations -depth first left first, very different from here used in answer) 

https://en.wikipedia.org/wiki/Merge_sort#Top-down_implementation -  Wikipedia 


 

---

k-way merge sort is exactly . what you're calling bottom-up approach..

Arjun sir i don't think merge sort is bottom-up by default. if i'm wrong please tell me.

in top down approach , you do like this

20 47 15 8 9 4 40 30 12 17  // now recursively divide the array until size becomes trivial

(20 47 15 8 9)                               (4 40 30 12 17)

(20 47 15)  (8 9)                      (4 40 30)            (12 17)

(20 47)  (15)  (8 9)                (4 40)    (30)          (12 17)

(20) (47) (15)(8)(9)               (4)(40)   (30)           (12)  (17)   // subproblem size becomes trivial

Now apply merge sort and combine sorted subproblems.

(20 47) (15) (8 9)                    (4 40) (30) (12 17)

(15 20 47)    (8 9)                     (4 30 40)  (12 17)

(8 9 15 20 47)                            (4 12 17 30 40)

                (4 8 9 12 15 17 20 30 40 47)

---

@Rupendra Choudhary, In 2 way merge, we split the array into 2 sub parts recursively right ? Just like in merge sort.

The default merge procedure is 2-way merge only.

According to your solution, in 2nd pass we get 8,9,15,20 at the beginning which is option a)

@Arjun sir , please clarify.

---

i provided no solution for this question. i just told how top down approach for merge sort works.in question they asked straight 2 way merge sort.Tell me from where you know what's default procedure for merge sort? straight 2-way is a variation of 2-way merge sort.approach for which is already told in form of answer by vikrant.

---

any heads up on what to use in the exam, I studied merge sort from CLRS and it's using the top down approach, recur and solve the left part first then the right part, and in addition to this how are the passes determined in the top down algorithm?

---

@ Vikrant Singh

can any one clarify what a pass exactly means?

because if pass means function exe then i think it would be different what is stated here.

Because as far as i know only first half portion of array is altered , not the entire array.

correct me if I am wrong

---

@ Rupendra Choudhary 
I too think Divide and Conquer algorithms should work in a top-down way by default. I mean shouldn't you first divide the lists before you start merging them if you call Merge-Sort Divide and Conquer?

Perhaps the term "elements" implies that our input was not a single list but separate sorted ones?
Maybe the word "straight" is supposed to mean you directly start merging the elements into sorted lists? At this point this seems more of an English question than an Algorithms one.

---

If this question is really asking for Straight 2 way merge sort, this is the procedure given by Knuth. But none of the answers is matching by following this method.

https://books.google.co.in/books?id=RlQqhEcLruUC&pg=PA162&lpg=PA162&dq=straight+two-way+merge+sort&source=bl&ots=dunjtRPWBX&sig=_DBjxmAT2Eb-dz9kWEJHejgeUyE&hl=en&sa=X&ved=2ahUKEwi_4_HhgKDfAhXPV30KHZA8Aq44ChDoATADegQIBxAB#v=onepage&q=straight%20two-way%20merge%20sort&f=false

---

I am not sure what the pass means here. if it means merging.. then shouldn't the answer be 15,20,47,8,9,4,40,30,12,17.

As per my understanding, first the mergesort algorithm will keep splitting the array recursively and continue further by taking the left part. i will then start merge from bottom up, including the right parts as it goes up. So first all of the left array would br sorted  followed by the right part and finally the last pass of merging.

 

---

We can draw recursion tree in 2 ways:

1) By being biased on the right sub-array during partition with odd number of elements. This would give 20,47,15,8,9,4,40,30,12,17 after 2 calls to merge function.

2) By being biased on the left sub-array during partition with odd number of elements. This would give 15,20,47,8,9,4,40,30,12,17 after 2 calls to merge function.

I think in the question they are talking about iterative mergesort. Reference: https://www.geeksforgeeks.org/iterative-merge-sort/

// Merge subarrays in bottom up manner.  First merge subarrays of
// size 1 to create sorted subarrays of size 2, then merge subarrays
// of size 2 to create sorted subarrays of size 4, and so on.
for (curr_size=1; curr_size<=n-1; curr_size = 2*curr_size) 
   { 
       // Pick starting point of different subarrays of current size 
       for (left_start=0; left_start<n-1; left_start += 2*curr_size) 
       { 
           // Find ending point of left subarray. mid+1 is starting  
           // point of right 
           int mid = min(left_start + curr_size - 1, n-1); 
  
           int right_end = min(left_start + 2*curr_size - 1, n-1); 
  
           // Merge Subarrays arr[left_start...mid] & arr[mid+1...right_end] 
           merge(arr, left_start, mid, right_end); 
       } 
       
   } 

By 2 passes they mean to say 2 iterations of the outer for loop in the above code.

First iteration of the outer for loop would merge all 1-sized array elements.

Second iteration of the outer for loop would merge all 2-sized array elements.

---

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

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