The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+20 votes
4.2k views

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:

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

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

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

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

asked in Algorithms by Veteran (59.4k points)
edited by | 4.2k views
0

Hi Guys,

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

0
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

1 Answer

+54 votes
Best answer

$20$   $47$   $15$   $8$   $9$   $4$   $40$   $30$   $12$   $17$
  \    /       \    /     \    /       \    /       \    /
 $20$ $47$    $8$  $15$    $4$ $9$    $30$ $40$   $12$  $17$    after $1$st pass
   \         /               \         /             \   /
    \       /                 \       /               \ /
$8,15,20,47$   $4,9, 30,40$    $12,17$     after $2$nd pass

Ans. B

answered by Boss (13.5k points)
edited by
+17
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.
+1
How the 2 way merge is different from the merge sort procedure
+1
0
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!
0
Merge sort is by default bottom-up. Anywhere have you seen top-down solution?
0

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 


 

+2
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)
+1
@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.
0
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.


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

35,507 questions
42,828 answers
121,691 comments
42,183 users