Merge Sort Algorithm Analysis

This report analyzes the Merge Sort Algorithm using iterative and recursive techniques. It includes experimental results, worst and average case scenarios, time and space complexity, and a conclusion.

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

4
MERGE SORT ALGORITHM ANALYSIS
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

5
MERGE SORT ALGORITHM ANALYSIS
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.
private static void generateWorstCase(int a[], int l, int r)
{
if (l < r)
{
int m = l + (r - l) / 2;
int[] left = new int[m - l + 1];
int[] right = new int[r - m];
split(a, left, right, l, m, r);
generateWorstCase(left, l, m);
generateWorstCase(right, m + 1, r);
join(a, left, right, l, m, r);
}
}

6
MERGE SORT ALGORITHM ANALYSIS
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

7
MERGE SORT ALGORITHM ANALYSIS
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.
Experimental Results
Worst Case Scenario
Recursive technique
Execution Time: 1.6 milliseconds

8
MERGE SORT ALGORITHM ANALYSIS
Steps:

9
MERGE SORT ALGORITHM ANALYSIS
Iterative technique
Execution Time: 7.97 milliseconds
Steps:

10
MERGE SORT ALGORITHM ANALYSIS
Average Case Scenario
Recursive technique
Execution Time: 1.5 milliseconds
Steps:

11
MERGE SORT ALGORITHM ANALYSIS
Iterative technique
Execution Time: 4.01 milliseconds
Steps

12
MERGE SORT ALGORITHM ANALYSIS
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

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

14
MERGE SORT ALGORITHM ANALYSIS
Appendices
Appendix 1
Source Code (JAVA)
import java.lang.Math.*;
class MergeSort_iterative {
public static void mergeSort(int a[], int n)
{
int i,j;
for (i=1;i<n;i=2*i)
{
for (j=0;j<n-1;j+=2*i)
{
int mid = j + i - 1;
int right = Math.min(j+2*i-1, n-1);
merge(a, j, mid, right);
}
}
}
public static void merge(int a[], int l, int m, int r)
{
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;
int left[] = new int[n1];
int right[] = new int[n2];
for (i = 0; i < n1; i++)
left[i] = a[l + i];
for (j = 0; j < n2; j++)
right[j] = a[m + 1+ j];
i = 0;
j = 0;
k = l;
while (i < n1 && j < n2)
{
if (left[i] <= right[j])
{

15
MERGE SORT ALGORITHM ANALYSIS
a[k] = left[i];
i++;
}
else
{
a[k] = right[j];
j++;
}
k++;
}
while (i < n1)
{
a[k] = left[i];
i++;
k++;
}
while (j < n2)
{
a[k] = right[j];
j++;
k++;
}
}
public static void display(int a[])
{
for (int i=0; i < a.length; i++)
System.out.print(a[i]+" ");
}
public static void main(String[] args)
{
int a[] = {22, 12, 15, 4, 7, 9};
System.out.print("Original array: ");
display(a);
mergeSort(a, a.length);
System.out.print("\n\nSorted array: ");
display(a);
}
}

16
MERGE SORT ALGORITHM ANALYSIS
Testing
INPUT EXPECTE
D OUTPUT
ACTUAL OUTPUT SUCCESS ANALYSIS
Input
array
length: 6.
Input
array
contents:
22, 12, 15,
4, 7, 9.
Expected
Output array
length: 6
Output
Array:
4 7 9 12 15
22
Both expected and actual
outputs have matched and
the test can therefore be
concluded as a
SUCCESS.

17
MERGE SORT ALGORITHM ANALYSIS
Appendix 2
Source Code (JAVA)
class MergeSort_Recursion
{
void merge(int arr[], int l, int m, int r)
{
int n1 = m - l + 1;
int n2 = r - m;
int left[] = new int [n1];
int right[] = new int [n2];
for (int i=0; i<n1; ++i)
left[i] = arr[l + i];
for (int j=0; j<n2; ++j)
right[j] = arr[m + 1+ j];
int i = 0, j = 0;
int k = l;
while (i < n1 && j < n2)
{
if (left[i] <= right[j])
{
arr[k] = left[i];
i++;
}
else
{
arr[k] = right[j];
j++;
}
k++;
}
while (i < n1)
{
arr[k] = left[i];
i++;
k++;
}
while (j < n2)
{
arr[k] = right[j];
j++;

18
MERGE SORT ALGORITHM ANALYSIS
k++;
}
}
void mergeSort(int a[], int l, int r)
{
if (l < r)
{
int mid = (l+r)/2;
mergeSort(a, l, mid);
mergeSort(a , mid+1, r);
merge(a, l, mid, r);
}
}
public static void display(int a[])
{
for (int i=0; i < a.length; i++)
System.out.print(a[i]+" ");
}
public static void main(String args[])
{
int a[] = {22, 12, 15, 4, 7, 9};
System.out.print("Original array: ");
display(a);
MergeSort_Recursion ob = new MergeSort_Recursion();
ob.mergeSort(a, 0, a.length-1);
System.out.print("\n\nSorted array: ");
display(a);
}
}
Testing
INPUT EXPECTED
OUTPUT
ACTUAL OUTPUT SUCCESS ANALYSIS
Input
array
length: 6.
Input
array
contents:
22, 12, 15,
4, 7, 9.
Expected
Output array
length: 6
Output
Array:
4 7 9 12 15
22
Both expected and actual
outputs have matched and
the test can therefore be
concluded as a
SUCCESS.

19
MERGE SORT ALGORITHM ANALYSIS
Appendix 3