Using the mergesort pseudocode in our textbook, sort the numbers 5, 2, 7, 4, 8,

Question

Using the mergesort pseudocode in our textbook, sort the numbers 5, 2, 7, 4, 8, 6, 3 in the ascending order. You should describe your answer as Figure 5.2 of our textbook. Note that our textbook’s example has 8 numbers. However, this problem has 7 numbers. Thus, you should read the pseudocode carefully and identify how it sorts the 7 numbers.

172 Divide-and-Conquer 5.1 Mergesort Mergesort is a perfect example of a successful application of the divide-and conquer technique. It sorts a given array A[0..n - 1] by dividing it into two halves A[0.. In/2J - 1] and A[[n/2J..n - 1], sorting each of them recursively, and then merging the two smaller sorted arrays into a single sorted one ALGORITHM Mergesort(A[0..n -1]) //Sorts array A[0..n - 1] by recursive mergesort //Input: An array A[0..n -1] of orderable elements //Output: Array A[0..n - 1] sorted in nondecreasing order ifn >1 copy Alo. In/2]-1] to Blo. In/2-1] copy Alln/2..n-1] to C[0..n/21-1] Mergesort(B[0.. Ln/2] 1]) Mergesort(C[0..n/21-1]) Merge(B, C, A) //see below The merging of two sorted arrays can be done as follows. Two pointers (array indices) are initialized to point to the first elements of the arrays being merged The elements pointed to are compared, and the smaller of them is added to a new array being constructed; after that, the index of the smaller element is incremented to point to its immediate successor in the array it was copied from. This operation is repeated until one of the two given arrays is exhausted, and then the remaining elements of the other array are copied to the end of the new array. ALGORITHM Merge(BI0..p1], C[0-4-1], Ap.p + q-1]) //Merges two sorted arrays into one sorted array //Input: Arrays B[0.p - 1] and C[O..q - 1] both sorted //Output: Sorted array A[0..p +q -1] of the elements of B and C while i

Explanation / Answer

Mergsort process is as follows:

                              5,2,3,4,8,6,3

                         5,2,3               4,8,6,3

                     5        2,3          4,8        6,3

                             2    3      4      8   6      3

                             2 ,3          4,8         3,6

                    5        2,3               3,4,6,8
                        
                        2,3,5                  3,4,6,8

                                2,3,3,4,5,6,8

Related Questions

Navigate

• Browse (All)
• Browse U
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.