Question

for the following array

30 5 40 11 20 9 15 2 60 25 80 3 73 35 4 75 20 6

1. Show the new array after each pass of Merge sort.
2. Show the new array after each pass of Quick sort.

Answer 1

ARRAY AFTER EACH PASS IS GIVEN IN UNDERLINE

A.) MERGE SORT

30 5 40 11 20 9 15 2 60 25 80 3 73 35 4 75 20 6(DIVIDED INTO TWO HALVES)

PASS 1 :30 5 40 11 20 9 15 2 60 25 80 3 73 35 4 75 20 6

PASS 2 :30 5 40 11 20 9 15 2 60 25 80 3 73 35 4 75 20 6

PASS 3 :30 5 40 11 20 9 15 2 60 25 80 3 73 35 4 75 20 6

PASS 4 :30 5 40 11 20 9 15 2 60 25 80 3 73 35 4 75 20 6

PASS 5 :30 5   40 11 20 9 15 2 60   25 80 3 73 35 4 75 20 6

PASS 6 :5 30 40 11 9 20 2 15 60 25 80 3 73 4 35 20 75 6

PASS 7 :5 11 30 40 2 9 15 20   60 3 25 80 73 4 20 35 75 6

PASS 8 :2 5 9 11 15 20 30 40 60 3 4 20 25 35 73 75 80 6

PASS 9 :2 5 9 11 15 20 30 40 60 3 4 6 20 25 35 73 75 80

PASS 10 : 2 3 4 5 6 9 11 15 20 20 25 30 35 40 60 73 75 80

B) QUICK SORT(PIVOT IS TAKEN AS THE LAST ELEMENT)

30 5 40 11 20 9 15 2 60 25 80 3 73 35 4 75 20 6

PASS 1 :5 2 3 4 6 30 40 11 20 9 15 60 25 80 73 35 75 20

PASS 2 :2 3 4 5 6 11 20 9 15 20   25 30 40 60 80 73 35 75

PASS 3 :2 3 4 5 6 11 9 15 20 20 25 30 40 60 73 35 75 80

PASS 4 :2 3 4 5 6 9 11 15 20 20 25 30 35 40 60 73 75 80

PASS 5 :2 3 4 5 6 9 11 15 20 20 25 30 35 40 60 73 75 80