What is meant by a pass in an Algorithm?

user_14044292 0
Viewed 473

I have came across a practice question from GATE PYQ's. The question asks about the pass in merge sort sorting algorithm. Below is the 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 [CORRECT OPTION]

C) 15, 20, 47, 4, 8, 9, 12, 30, 40, 17

D) 4, 8, 9, 15, 20, 47, 12, 17, 30, 40

I am just not able find out what is meant by pass and how to find it in this case.

Distribution of elements in the recursive calls:

         20, 37, 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

After sorting:

           4 ,8, 9, 15, 12, 17, 20, 30, 40, 47 
                 /                     \
     8, 9, 15, 20, 47               4, 12, 17, 30, 40
       /        \                     /          \
 20, 15, 47     8, 9              4, 30, 40      12, 17
    /    \
20, 47   15
mergesort recursion sorting algorithm
1 Answers

The usage of the term pass implies that the question is asking about bottom up merge sort which starts by treating an array of n elements as n runs of size 1. Each pass merges even and odd runs, doubling the size of runs (except for the last run which may be shorter). The sort is done when run size >= number of elements.

|20|47|15| 8| 9| 4|40|30|12|17|   start
|20 47| 8 15| 4  9|30 40|12 17|   after pass 1
| 8 15 20 47| 4  9 30 40|12 17|   after pass 2
| 4  8  9 15 20 30 40 47|12 17|   after pass 3
| 4  8  9 12 15 17 20 30 40 47|   after pass 4, done
user_32820560
Related