Goal:

Compare the performances of Bubble Sort and Merge Sort.

Requirement:

A. Modify the reference program at the bottom in this way.

1. Complete mergeSort () so that the we can see the array is sorted.
2. Create an array of 1000 random numbers.
3. Use Merge Sort to sort the array.
4. Get the number of key comparisons for the sorting.
5. The total of the number of key comparisons should be returned to main().

B. Do merge sort five times and calculate the average of these five numbers of key comparisons. Display a report similar to the following one.

	# of key comparison
1	8726
2	8707
3	8708
4	8688
5	8678
==============	=========================
Average	8701

C. Use Bubble Sort to sort 1000 random numbers and generate a report like the one above.

Discussion:

The purpose of this program is for testing the performances of Merge Sort and Bubble Sort.

Based on the theory, the time complexity of Bubble Sort is N*N. The actual number should be between (300*1000) to (500*1000). (Could you give the reason why it is not close to 1000*1000?) The time complexity of Merge Sort is N*Log(N).

With the two reports, we can see that the average of the key comparisons of Bubble Sort is about 450*1000, and that of Merge Sort is about 9*1000. With these numbers we can conclude that Merge Sort is roughly 50 times faster than Bubble Sort in the case that the array has 1000 elements.

Reference program:

#include

using namespace std;

void merge(int arr[], int l, int m, int r)

{

int i, j, k;

int n1 = m - l + 1;

int n2 = r - m;

/* create temp arrays */

int L[n1], R[n2];

/* Copy data to temp arrays L[] and R[] */

for (i = 0; i < n1; i++)

L[i] = arr[l + i];

for (j = 0; j < n2; j++)

R[j] = arr[m + 1+ j];

/* Merge the temp arrays back into arr[l..r]*/

i = 0; // Initial index of first subarray

j = 0; // Initial index of second subarray

k = l; // Initial index of merged subarray

while (i < n1 && j < n2)

{

if (L[i] <= R[j])

{

arr[k] = L[i];

i++;

}

else

{

arr[k] = R[j];

j++;

}

k++;

}

/* Copy the remaining elements of L[], if there are any */

while (i < n1)

{

arr[k] = L[i];

i++;

k++;

}

/* Copy the remaining elements of R[], if there are any */

while (j < n2)

{

arr[k] = R[j];

j++;

k++;

}

}

/* l is for left index and r is right index of the

sub-array of arr to be sorted */

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

{

/// ADD YOUR CODE HERE

}

void printArray(int A[], int size)

{

int i;

for (i=0; i < size; i++)

printf("%d ", A[i]);

printf(" ");

}

int main()

{

int arr[] = {12, 11, 13, 5, 6, 7, 4, 343, 5, 6, 78, 2, 34, 22, 111, 35, 78, 79};

int arr_size = sizeof(arr)/sizeof(arr[0]);

printf("Given array is ");

printArray(arr, arr_size);

mergeSort(arr, 0, arr_size - 1);

printf(" Sorted array is ");

printArray(arr, arr_size);

return 0;

}