FastKid12 - 7 months ago 33

C++ Question

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.