CM2100 Advanced Software Design and Development

In this coursework, you are to carry out an analysis of two different versions of the merge-sort algorithm by performing a number of experiments.  You will present the results of these experiments in a short report that relates the results to the theoretical performance for both versions of the algorithm.  

Implement the recursive merge-sort algorithm which was introduced in lectures, and measure its performance for different sizes of array to be sorted.To measure its performance you should measure:

• the number of comparisons it performs
• the number of copies it performs
• the number of recursive calls.

• How were the experiments performed?  
• What sort of data was used?
• How was that data generated to test average case performance?
• How was that data generated to test worst case performance?
• Include a description of how the two versions of the merge-sort algorithm were tested
• Results of the first experiment
• how does the number of operations vary with different sizes of arrays used, include tables to show the data obtained showing counts of copies and comparisons required. Include appropriate graphs to illustrate the results.

• State what the theoretical performances of the algorithms for the two experiments should be under average and under worst-case scenarios
• Comparison between the results and the theoretical performances of the algorithms for the two experiments
• Your analysis should demonstrate convincingly and rigorously any conclusions you make about whether the results match theory
• Comparisons between the two methods

Answer:

Introduction

• Bubble sort
• Selection sort
• Insertion sort
• Merge sort

Here in this report, the merge sort technique has been taken up for review and the two types of merge sort a

lgorithms which are the iterative merge sort technique and the recursive merge sort technique. Furthermore, light will be thrown on both of these algorithms and their time complexities are to be measured and analyzed to conclude about which among the two techniques would be suitable. In order to complete this test, several data sets of different data types are to be generated and then these data sets are to be sorted based on both the algorithms. While generating the data sets, the best case, average case and the worst case scenarios shall also be considered.

Experimental Method

The Merge Sort algorithm

Both the merge sort algorithms have been converted into JAVA program codes and have been presented below with their optimal output screenshots and a simple input/output analysis to figure out whether the desired output is obtained for a particular set of dummy data or not. The graphical representation of a sample merge sort operation has been presented in Appendix 3.

Iterative Algorithm

In this mechanism of merge sort, the complete array is treated as a collection of several smaller arrays which are already sorted. Then, these smaller arrays are gradually merged to form arrays of double their size. Every small array pieces are sorted individually at each turn and are then merged back into the main array. Finally when all the smaller arrays are sorted individually and merged as one, the array thus formed is seemed to have been already sorted. All these breakdowns and merging is achieved through the use of iterative FOR loop block statements. The merge sort algorithm using the iterative method has been presented in Appendix 1. A simple test case has also been provided.

Recursive algorithm

Iterative technique

Merge Sort Analysis

The time complexity of the Merge sort algorithm is O (n Log n). This can be achieved through deriving the equation from the basic concept of time usability of the processes. As it is clear from the above explanations that each array at each and every level is divided into two more sub-arrays.

T(n) = T(n/2) + T(n/2) + θ(n)

Conclusion

From the above report it can be concluded that both the algorithms thrive to produce the same output no matter what. However, as it can be seen from the experimental outputs, the average case scenarios perform better in terms of time consumption for execution when compared to the worst case scenarios, for both algorithms. Also, it can be seen that the execution time needed for the recursive algorithm and that for the iterative technique differs in all cases. The larger the data set, the lesser is the difference of execution time and it can be stated that the execution time in Iterative method will be lesser than that of the recursive method when enormous data sets are concerned, also the recursive technique uses up a major part of the stack and hence is also considered to use more memory. On behalf of the recursive technique, it can be stated that the recursive technique has a more modified version of the code that is short and better understandable if the concept is clear. In addition to that, the recursive technique is a preferred technique over iterative methods when it comes to traverse data lists to reach a particular state and then trace back. Hence, recursion is more elegantly used in this case.