You are asked to modify the textbook(introduction of algorithm by cormen) versio

Question

You are asked to modify the textbook(introduction of algorithm by cormen) version of Merge-Sort on page 31 into a new algorithm of Merge-Triplet-Sort. In Merge-Triplet-Sort, an input array A will be split into three equal-sized sub-arrays L, M, and R that stands for left, middle, and right. a. Please revise the textbook pseudocodes of Merge-Sort() and Merge() functions for your Merge-Triplet-Sort algorithm. b. Please find the analytical time complexity of Merge-Triplet-Sort using elimination method. You must show your procedure.

Explanation / Answer

Merge Sort is a sorting technique based on divide and conquer technique with comparison.

In mergesort we sort the unsorted list into n sublists
Worst Case performance: O (n log n)
Best case Performance: O (n log n) for typical O(n)

A is an Array of unsorted elements.
p and r are the indxs of the array p is starting and r is ending and q is index between p and r

MergeSort(A, p, r)
    If p > r
        return;
    q = (p+r)/2;
    mergeSort(A, p, q)
    mergeSort(A, q+1, r)
    merge(A, p, q, r)
In the above we discussed abouth the merge sort a traditional approach.

But as per the given modifications

The array is divided into three equal subparts

Take the array of unsorted elements:A

Count the Index (A);

In the next step we can divide the
L,M,R arethe array subparts

In this the above algorithm divides into three parts eaxh part is sorted individaully
Sort each array subpart
sort(L)
Sort(M)
Sort(R)

merge(L,M,R);
The time complexity of the Mergesort is O(n logn)
for Merge sort triplet time complexity is O(n)
it reduces the sorting time for the array.

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

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