GATE 1999 Example on Merge Sort

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
\)

 

Answer

\(\underline{\textbf{Things you need to know}}\)

Refer: http://www.techtud.com/video-lecture/merge-sort-algorithm-analysis-and-p...

Now,

Input :                                                                        \(20, 47, 15, 8, 9, 4, 40, 30, 12, 17
\)

\(I^{st}-Pass\):                                                             20, 47, 8, 15, 4, 9 , 30, 40, 12, 17

\(II^{nd}-Pass\):                                                          8, 15, 20, 47, 4 , 9, 30, 40, 12, 17

 

\(\therefore \) Ans (B)

 

0Comment