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.

Experimental method

• 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.

Analysis of 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

Introduction

A sorting algorithm consists of a series of conditional and iterative instructions that takes a list or array of elements as an input and then specified operations on them and finally produces a sorted array. The sorting algorithms can be used with any types of data and sort them according to the needs of ascending or descending order. The sorting techniques can be further used in solving various programming problems. There are many sorting techniques that are widely used all over by programmers to sort their sorting needs. These are mainly listed as below:

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

Each of these sorting techniques has their own logic sequence and hence can be coded with different algorithms. Therefore, the time complexities of each also varies.

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

Furthermore, the results from the tests are to be critically analyzed with their relations or differences to the theoretically expected performances. Graphs and result tables shall be presented according to the results of the analysis and a conclusion about the same is to be reached.

Experimental Method

Before moving forward with the experiment, it is necessary to discuss the details of the two algorithms that are in highlight in this report. The definitions and the process of the two algorithms shall be clearly stated and then their source code shall be presented. This source code of the algorithm will be written using the Java language, compiled and executed in the NetBeans IDE. Furthermore, the inputs and outputs of the programs will be separately tested for a set of basic data to examine the righteousness of the code. The time and space complexities of the algorithms will be determined and presented for analysis.

In order to assist in the process of the analysis of the two algorithms, narrow amendments in the code has been made that will allow the system to record the time of execution for each process and also display the intermediate steps that the program goes through. This will help the analysis in many a ways. Firstly, through the execution time stamp, the time complexity of the programs can be portrayed and contrasted against each other. Secondly, the intermediate steps will allow to view the inner breakdown steps that differentiates the two algorithms and hence would allow the analysis process to conclude the better suiting one from the two. The test cases that will be used for both the worst and the average case scenarios.

The test case data sets were generated using an external method that is automatically operated based on the user’s input. This input method takes in n number of elements into an array which is either manually entered or generated using a random number generator or sequence generator program. The average case scenario is to be tested using a general set of data, where the size of the test cases or the array size will be pre-determined and the values will be entered at compile time, which will be in descending order. Secondly for the worst case, the data for the array will be created using the in-built methods which will be designed in such a way that the data in the array will be in a special way to generate the worst case. In order to generate the worst case of merge sort, the merge operation that resulted in above sorted array should result in maximum comparisons. The left and right sub-arrays involved in the merge sort operation should store alternate elements of a sorted array for example {10, 20, 30, 40, 50, 60, 70, 80}. Therefore, the left sub-array should be {10, 30, 50, 70} and the right sub-array should be {20, 40, 60, 80}. Now every element of the array will be compared at-least once and that will result in maximum comparisons. We apply the same logic for left and right sub-array as well. For array {10, 30, 50, 70}, the worst case will be when its left and right sub-array are {10, 50} and {30, 70} respectively and for array {20, 40, 60, 80} the worst case will occur for {20, 40} and {60,80}. This data set will be consisting of a large number of elements to test the algorithm at the array’s utmost state. A modified code snippet will be used in generating the worst case array whose main operational method is as follows.

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

The Recursive Merge Sort is also a Divide and Conquer algorithm, however unlike the iterative method, this method uses the recursion technique in order to achieve the sorted output. The recursive sort method divides the input array in two halves, then calls itself for the two halves and keeps dividing until the arrays consist of single elements only. Then merges the two sorted halves. The mergeSort() function is used for merging two halves. The merge(a, l, m, r) is a key process that assumes that a[ left .... mid ] and a[ mid+1 .... right ] are sorted and merges the two sorted sub-arrays into one unless the array of the original size is obtained, which is then sorted. Both these merge sort algorithms produces the same output but there are performance differences which will be discussed in details in a later section. The merge sort algorithm using the iterative method has been presented in Appendix 2. A simple test case has also been provided.

Iterative technique

Execution Time: 4.01 milliseconds

Steps

Merge Sort Analysis

Time Complexity

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)

This is the recurrence equation of the time complexity for the merge sort algorithm can be solved to produce the overall time complexity for it, that is θ (n*log n), that is n numbers of recursions or iterations are handled, each of complexity (log n).

It is to be noted that the time complexity remains fixed for each of best, average and worst case scenarios.

Space Complexity

The space complexity of a merge sort algorithm depends on various factors. For the examples that have been used above, the space complexity would be O(n). In this case as well, the space used up by the iterative method of merge sort can be calculated to be O(n) as at each step, twice the number of arrays are generated to further reach n number of singular element arrays. The sub-arrays generated in the upper levels are generally destroyed due to the recursive calls that clear the stack and destroy the memories assigned.

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.