If one uses straight two-way merge sort algorithm to sort the following…

2015

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. A.

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

  2. B.

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

  3. C.

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

  4. D.

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

Attempted by 233 students.

Show answer & explanation

Correct answer: B

Straight two-way merge sort merges adjacent subarrays in passes.

Pass 1 merges pairs of size 1 into sorted subarrays of size 2: [20, 47], [8, 15], [4, 9], [30, 40], [12, 17].

Pass 2 merges adjacent sorted subarrays of size 2 into groups of size 4: [8, 15, 20, 47], [4, 9, 30, 40], and the remaining [12, 17].

The order of elements after the second pass is 8, 15, 20, 47, 4, 9, 30, 40, 12, 17.

Explore the full course: Isro