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.
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.
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.
Topic: Algorithms and Data Structures II 1. Given : L = {23, 17, 14, 6, 13,...