The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+21 votes
4.9k 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.7k points)
edited by | 4.9k 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
0
is k way merging different than merging k sorted arrays??
0
whats the correct way to make initial groups to sort?
k way means start from beginning and make set of every 3 elements?

1 Answer

+63 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

Answer is B.

answered by Boss (13.5k points)
edited by
+19
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 


 

+7
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.
0
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?
0

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

0

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.

0
Answer:

Related questions



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

44,255 questions
49,750 answers
164,116 comments
65,848 users