Merge Sort Algorithm Analysis

Running head: MERGE SORT ALGORITHM ANALYSIS
Merge Sort Algorithm Analysis
Name of the student:
Name of the University:
Author note:

1
MERGE SORT ALGORITHM ANALYSIS
Table of Contents
Introduction................................................................................................................................2
Experimental Method.................................................................................................................3
The Merge Sort algorithm......................................................................................................5
Iterative Algorithm.............................................................................................................5
Recursive algorithm...........................................................................................................5
Experimental Results.................................................................................................................6
Worst Case Scenario..............................................................................................................6
Recursive technique...........................................................................................................6
Iterative technique..............................................................................................................8
Average Case Scenario..........................................................................................................9
Recursive technique...........................................................................................................9
Iterative technique............................................................................................................10
Merge Sort Analysis.................................................................................................................11
Conclusion................................................................................................................................11
Appendices...............................................................................................................................13
Appendix 1...........................................................................................................................13
Appendix 2...........................................................................................................................16
Appendix 3...........................................................................................................................18

2
MERGE SORT ALGORITHM ANALYSIS

3
MERGE SORT ALGORITHM ANALYSIS
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 algorithms 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.
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