Question

A new implementation of Merge Sort uses a cutoff variable to use insertion sort for small number of items to be merged (Merging single elements is costly).

1. Give the pseudo code for the merge sort algorithm with a cutoff variable set to 4.

2. Show the trace for top-down merge sort using the following array of characters with a cutoff variable set to 4.

E A S Y M E R G E S O R T W I T H I N S E R T I O N

Answer 1

Note:

AS PER OUR PROBLEM,IF ARRAY SIZE <=4,ITS ALWAYS SORTED.

SO TO SORT THOSE ARRAYS WE IMPLEMENT A FUNCTION TO SORT THEM.

Pseodo code:-

void mergeSort(int arr[], int l, int r)

{

  if (r - l + 1 > 4)//if arraysize>cutoff size only

    {

        int m = l + (r - l) / 2;

        mergeSort(arr, l, m);

        mergeSort(arr, m + 1, r);

        merge(arr, l, m, r);//function to combine to sorted arrays

    }

else //array size is <= cutoff size

sort( arr , l , r); //function to sort the array whose size<=cutoff size

}