Modify Merge in such a way that the MSort runs in time O(n log k) and the first

Question

Modify Merge in such a way that the MSort runs in time O(n log k) and the first k numbers in the sorted order are computed correctly. Explain why the algorithm is correct and why its running time is O(n log k).

(Infor on MSort)

Function MSort(A, n, B) sorts < A, n > and it uses < B, n/2 > as the extra space. We will also
use the auxiliary recursive function AMSort(A, n, B) that sorts < A, n > with the result that occupies
< B, n >, without other extra space.

MSort(A,n,B) { // merge sort with auxiliary space B
if (n < 4)
InsertSort(A,n);
else {
h = n/2; // rounded down if n is odd
AMSort(A,h,B);
MSort(A+h,n-h,A);
Merge(B,h,A+h,n-h,A);
}
}

AMSort(A,n,B) { // merge sort into auxiliary space B, n > 1
h = n/2; // rounded down if n is odd
MSort(A,h,B);
MSort(A+h,n-h,B);
Merge(A,h,A+h,n-h,B);
}

Explanation / Answer

Faster merge. Implement a version of merge() that copies the second half of a[] to aux[] in decreasing order and then does the merge back to a[]. This change allows you to remove the code to test that each of the halves has been exhausted from the inner loop. Note: the resulting sort is not stable.

  private static void merge(Comparable[] a, int lo, int mid, int hi) {      for (int i = lo; i <= mid; i++)        aux[i] = a[i];           for (int j = mid+1; j <= hi; j++)        aux[j] = a[hi-j+mid+1];         int i = lo, j = hi;      for (int k = lo; k <= hi; k++)         if (less(aux[j], aux[i])) a[k] = aux[j--];        else                      a[k] = aux[i++];  }   

Related Questions

Navigate

• Browse (All)
• Browse M
• Subjects

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