Question

Topic: Algorithms and Data Structures II

1. Given : L = {23, 17, 14, 6, 13, 10, 1, 5, 7, 12} ... do the following

a. Perform a mergesort. Split it systematically. ( ex. 4x4, 2x2 ). Use indicators to show the split. Use (2^k) * (2^k) merge boxes.

b. Explain how mergesort works in steps.

c. Write the Pseudo Code of this.

--

Explain this clear and simple please.

Answer 1

Merge sort is a sorting technique based on divide and conquer technique. With worst-case time complexity being ?(n log n), it is one of the most respected algorithms.

Merge sort first divides the array into equal halves and then combines them in a sorted manner.

23,17,14,6,13,10,1,5,7,12

We know that merge sort first divides the whole array iteratively into equal halves unless the atomic values are achieved. Array will divide after calculating a middile point, middle point will be (start of array +end of array/2).Here start of array is 0 and end of array is 0 so the middle point will be (0+9/2)=4 (it will take integer value). Value at the index 4 is 13.We can see here that an array of 10 items is divided into two arrays of size 5

Here with am attaching screenshot of split and merge array. In screen shot the no in bold is splitter.
Fil: Ei Source Re Navigste Sr Project R.n Wndow Hedp ntegerButt //terCas twn suharcny5 nf烈r.11 // G rtr肿般hncray、ts赧r[1..n] 5erend刕.h"CCMF ㅓ®, accle+1..r] // nt ] new int [n] i" verge the teen,array, // Tn1+1n1 ㅓ nceXP『 nf ftr,中 "nd 'erond 烈hMTTMX忌 // Tn1t1n1 1ncex f narCh1穀harry "rrmy Given rsy 156718 12 3 14 17 23 O lype hene to search ENG INT 1-0-

Catng value). Value at the Index 4 Is 13.We can see here that an array of 10 Items is divided Into two arrays of size 5. 1 step 1015712 3 17 146 13 2 step 6,13 10,1.5 7,12 23,17,14 12 step 13 10,1 23,17 14 4 step 10 23 17 5 step 1,10 7, 12 17.23 6,13 6step 1,5,10 14,17,23 7 step 1,5,10,7,12 6,13,14,17,23 8 step 1,5,6,7,10,12,13,14,17,23 Step-1 array will divide in 2 parts again. Here middle point is (0+4/2) 2.vae of aray at index 2 NG 652 Tpe here to searchh

Description of steps

Step-1 array will divide in 2 parts again. Here middle point is (0+4/2)=2.value of array at index 2 is 14.

In second array middle point is (5+9/2) =7.value of array at index 7 is 15.

Step-2 . Here middle point is (0+3/2)=1.value of array at index 1 is 17.

In second array middle point is (3+4/2) =3.value of array at index 3 is 6.

In third array middle point is (5+7/2) =6.value of array at index 6 is 1.

In second array middle point is (8+9/2) =8.value of array at index 8 is 7.

Now which array is atomic will not divide further but which are not atomic will divide further.

Step-3 array will divide in 2 parts again. Here middle point is (0+1/2)=0.value of array at index 0 is 23.

In second array middle point is (5+6/2) =5.value of array at index 5 is 10.

Step -4 Here all elements are atomic.now we will combine there array after sort them.

Step-5 Here 4 sorted arrays will be create after merging 2 elements.

Step-6 Here 2 sorted arrays will be create after merging 3 elements.

Step- 7 Here 2 sorted arrays will be create after merging 5 elements.

Step- 8 1 merged 10 elemnts sorted array.