FastKid12 FastKid12 - 1 month ago 8
C++ Question

Type Of Merge Sort Confusion

I am asked to write two types of merge sorts. One is a binary merge sort with time theta(n lgn) and a natural merge sort with time O(n lgn). I have searched everywhere to understand what each of them do. I am having trouble understanding the differences, I just need some explanation or examples would be great. I have written a merge sort but what I have is it a natural or binary merge sort?

bool compareElements(int i, int j)
{
++COMPARE_COUNT;
//int *t = i;
return i < j;
}
void merge(int values[], int left[], int right[], int middle, int total)
{
int left_size = middle, right_size = total - middle;
int i = 0, j = 0;

// Loop through values array
for (int k = 0; k < total; k++)
{
// If elements left on left and either no elements on right
// or left is larger than right, then use next left value
if (i < left_size && (j >= right_size || left[i] <= right[j]))
{
values[k] = left[i];
i++;
}
// else use next right value
else
{
values[k] = right[j];
j++;
}
}
}
void mergeSort(int values[], int n,bool result)
{
if(result == false)
{
if (n < 2)
{
return;
}
int middle = n / 2;
int *left = new int [middle];
int *right = new int [n - middle];

for (int i = 0; i < n; i++)
{
//COMPARE_COUNT++;
if(compareElements(i,middle)) //(i < middle)
{
SWAP_COUNT++;
left[i] = values[i];
}
else if(!compareElements(i,middle))
{
SWAP_COUNT++;
right[i - middle] = values[i];
}
}
mergeSort(left, middle,result);
mergeSort(right, n - middle,result);
merge(values, left, right, middle, n);
}
}

Answer

A binary merge sort has a very simple recursive definition: split the input array into two halves, sort the two halves using binary merge sort, merge the two halves into a sorted sequence. This is what you implemented.

A different version is a bottom-up merge sort. This first splits a sequence up into subsequences of length 1, and then starts merging them.

A natural merge sort has a different first step. It doesn't split the input sequence into halves, but into runs. A run is a sequence of elements that are increasing or decreasing. For example the following array:

0 1 4 2 3 9 8 7 5 2 1 3 4 2 4 3 4

Can be split into runs like this:

0 1 4 | 2 3 9 | 8 | 7 | 5 | 2 | 1 3 4 | 2 4 | 3 4

Where each run is is already ascending. Then you start merging runs as if you would in merge sort, except you merge from the bottom up.

The reason this is called a natural merge sort is that if your input is already (partially) pre-sorted, the algorithm will start to approach a O(n) best case performance.

Comments