Project 2 involves an analysis of the results that you obtained in first project. You are to submit a paper, written with Microsoft Word, that discusses the results of your analysis. Grading of the...

Q1. A brief introduction of the sorting algorithm that you have selected and how the two versions of the
algorithm compare?
Ans.
A. I have selected Merge sort algorithm in previous project.
Merge sort algorithm :
Merge sort is an example of the divide and conquer.
 Merging Is the process of combining two sorted files to make one bigger sorted file.
 Selection is the process of dividing a file into two parts: k smallest elements and n-k largest
elements.
 Selection and merging are opposite operations. Selection splitsa list into two listes and merging
joins two files to make one file.
 Merger sort divide the list into two parts, then each part is conquered individually. Merge sort
starts with the small sub files and finishes with the largest one. As a result it doesn’t need stack
and this algorithm is stable.
B. Algorithm comparisons: Let us assume that we expressed running time of given algorithm as a
function of the input size n(i.e. f(n)) and compare these different functions corresponding to running
times. This kind of comparisons is independent of machine time, programming style, etc.
Sorting algorithms are usually judged by their efficiency. In this case, efficiency refers to the algorithmic
efficiency as the size of the input grows large and is generally based on the number of elements to sort.
Most of the algorithms in use have an algorithmic efficiency of either O(n^2) or O(n*log(n)). A few
special case algorithms can sort certain data sets faster than O(n*log(n)). These algorithms are not
based on comparing the items being sorted and rely on tricks. It has been shown that no key-
comparison algorithm can perform better than O(n*log(n)).
Many algorithms that have the same efficiency do not have the same speed on the same input. First,
algorithms must be judged based on their average case, best case, and worst case efficiency. Some
algorithms, such as quick sort, perform exceptionally well for some inputs, but horribly for others. Other
algorithms, such as merge sort, are unaffected by the order of input data. Even a modified version of
bubble sort can finish in O(n) for the most favorable inputs.
A second factor is the "constant term". As big-O notation abstracts away many of the details of a
process, it is quite useful for looking at the big picture. But one thing that gets dropped out is the
constant in front of the expression: for instance, O(c*n) is just O(n). In the real world, the constant, c,
will vary across different algorithms. A well-implemented quicksort should have a much smaller constant
multiplier than heap sort.
A third criterion is...