mergesort

Question

Given the following list of numbers:

[21, 1, 26, 45, 29, 28, 2, 9, 16, 49, 39, 27, 43, 34, 46, 40]

which answer illustrates the list to be sorted after 3 recursive calls to mergesort?

[16, 49, 39, 27, 43, 34, 46, 40]
[21,1]
[21, 1, 26, 45]
[21]

Answer 1

when the mergesort firstly runs it breaks the list in two parts

part1 = 21, 1, 26, 45, 29, 28, 2, 9

part2 = 16, 49, 39, 27, 43, 34, 46, 40

now first recursive call will take part1 as input and break into again two parts

part1.a = 21, 1, 26, 45

part1.b =  29, 28, 2, 9

now second recursive call will take part1.a  as input and break into again two parts

part1.a.1 =  21, 1

part1.a.2 = 26, 45

now third recursive call will take part1.a.1 as input and break into again two parts

part1.a.1.x =  21

part1.a.1.y =  1

so answer is 21

Comments

check ones 21 will be after 3 rd or 4rd recursive call ?

---

Yes ManojK

21 will be after 4th..I think.

After third recursive the array to be sorted will be [21,1].

---

initially we call mergesort in code then input is
21, 1, 26, 45, 29, 28, 2, 9, 16, 49, 39, 27, 43, 34, 46, 40
recursive call mergesort (21, 1, 26, 45, 29, 28, 2, 9) ------ 1
recursive call mergesort (21, 1, 26, 45) -------- 2
recursive call mergesort(21, 1) ------- 3

---

after a call means, the call is completed- so here should be just before 5th recursive call.

Answer 2

answer is D)

Comments

"after 3rd recursive call",

---

initially we call mergesort in code then input is
21, 1, 26, 45, 29, 28, 2, 9, 16, 49, 39, 27, 43, 34, 46, 40
recursive call mergesort (21, 1, 26, 45, 29, 28, 2, 9) ------ 1
recursive call mergesort (21, 1, 26, 45) -------- 2
recursive call mergesort(21, 1) ------- 3

---

Oh thanks. Hadn't noticed that.