Merge Sort Analysis

The merge sort algorithm is a stable sorting technique with an average time complexity of O(n log n) and space complexity of O(n). It uses divide-and-conquer approach to sort an array of size 'n'. The algorithm recursively divides the array into two halves, sorts them using the same approach, and then merges the sorted sub-arrays. This process continues until the array is fully sorted. Additionally, there are cache-aware versions of merge sort that optimize performance by minimizing page movements in memory caches.

Merge sort is an effective sorting algorithm based on comparison. The algorithm is based on
"Divide and conquer," meaning the initial collection will be split into smaller pieces in this
situation. This concept can be introduced recursively so that the collection is split into single
components and then rebuilt into a sorted set. The re-construction of the algorithm merging
portion is the phase where the components are ordered. In each phase of merge sort, the
components are placed in the positions they have sorted, in the sub-collection. Distributing the
authentic collection into its elements may lead to the formation of additional elements which are
essentially not required. The handling of the sub-collections may be in place so that distinct
collections are not required.
There are different variants that exists regarding merge sort. These variants are mainly worried
with decreasing the complexity of storage and the price of copying.
A simple solution to minimize the space of overhead to n/2 is to keep left and right of the array
as a structure which seems to be combined but are actually not. Then into the temporary or
cached space, a copy of the left part m is made and then routine of merge is directed to place the
output of the merged sort in m. In order to make use of only one allocation in the memory, it is
good to give temporary room outside the merge routine with this variant. As the last couple of
lines before the return result declaration becomes superfluous, the unnecessary copying listed
above is also mitigated.
When applied on arrays, one drawback of merge type is its O(n) requirement of memory for its
operation. Several variants were suggested in-place:
 There is an algorithm that needs a steady quantity of working memory: sufficient storage
space to hold an input array element, and extra space to hold O(1) pointers in the input
array. These algorithm are said to be not stable but yet they are able achieve an O(n log
n) time in spite of being unstable.
 There have been several attempts to create an in-place merge algorithm that can be
combined with a conventional merge type (bottom up or top-down) to establish an in-
place merge type. In this case, in-place would mean taking of the logarithmic space of the
stacks, since the standard type of merge requires that amount of space for its own use.
Stable merging is possible with a constant amount of scratch space in O(n log n) time, but
yet again this algorithm is also complicated and has high factors of consistency: merging

lengths n and m can take 5n + 12 m + o(m) movements. This factor of high constant and
complex nature of the algorithm has been produced easier to comprehend and simpler. A
simple linear time algorithm known as in-place practical merging is implemented to
merge a sorted list using a set quantity of extra space. It will be helping in merging the
linear time and at the same time providing a continues space allocation.
 An option to reducing copying to various lists is to combine a fresh data field with each
key (keys are called the elements in m). This field will be used to connect the keys and
any related data in a sorted list (record is called a key and its related data). Then the
merging of the sorted lists takes place by altering the values of the link; there is no need
to move documents at all. A field containing only a connection will usually be larger than
a whole record, so less room will be used as well. This is a normal method of sorting, not
limited to sorting done through the use of merge sort.
Natural merge sort
A natural type of merge is comparable to a kind of bottom-up merge except that any naturally
occurring runs (sort sequences) are utilized in the input. Both bitonic as well as monotonic runs
can be utilized, with lists being convenient data structures (use as LIFO or FIFO). The starting
point assumes that each run is one item long in the bottom-up merge type. In practice, there will
be many brief runs of random input information that just occur to be sorted. In the typical
situation, because there are fewer runs to merge, the natural merge type may not need as many
passes. In the best case, the input is already sorted (i.e. single run), so it only needs to make one
pass through the data by the natural merge sort. Long natural runs are present in many practical
instances, which is why natural merge type is utilized.
Process
The process of merge sort involves three parts
 Dividing the issue into a number of smaller subproblems of the same issue.

 Conquering the subproblems by continuosly solving them. Solve the subproblems as
basic cases if they are small enough.
 Combine the subproblem alternatives into the initial issue solution.
Performance analysis
The merge sort algorithm output is very remarkable O(n log(n)). It is suggested to use a default
library. Most languages nowadays use a better performing algorithm as the default sorting
alternative in a true world implementation. In Java, there is a sort technique in the Util package,
in the Arrays class. Dual-Pivot Quicksort, which conducts O(n log(n)) time complexity, is
implemented based on the documentation.
According to the below Java code, in the function mergeSort, only two statements can create
extra space. One is center, which requires complexity of O(1) space. The other is merge feature,
which due to the presence of a temporary array(tem) requires O(n) space complexity. The
algorithm is also a deep-first algorithm. At some stage there is only one merge feature that can be
performed. Hence, the complexity of room here is O(n).
The median and worst-case performance of Merge Sorting n objects is O(n log n). Considering
time of the merge sort for a length n list while it is in a running state is T(n), then the recurrence
T(n)= 2T(n/2)+n follows from the algorithm definition which asks to put the algorithm to half
the size of the two lists of the initial list and then the n steps made to merge the two output lists

are added. The closed form follows from the dividing-and conquering recurrences master
theorem.
As multilevel memory hierarchies are used, location of reference can be of paramount
significance in software optimization on contemporary pcs. Some of the existing algorithms of
merge sort which are mostly aware of the cache memory of the machine are introduced, whose
tasks are notably selected to reduce the pages movements that take place from the cache machine
as well as outside the machine. For example, when subarrays of size S are reached, the merge
sort having the tiled algorithm will immediately stop to divide the subarrays, where S is said to
be the amount of cache memory that the machine or the CPU can hold. In order to prevent the
memory from getting wrapped or no longer accessible, a sorting algorithm such as the insertion
sort is used in this place first in order to have no cache memory issues and then with the mode of
standard recursion, merge sort is then finally performed over it in order to get it sorted in the
given manner be ascending or descending. On computers that profit from cache optimization,
this algorithm has proved better efficiency.

Implementing merge sort
The function of merge sort should sort the subarray array [p. r] recursively. It means after
calling merge sort on (array, p, r), the components should be sorted in ascending order from
index p to index r of the array.
The algorithm of merge sort explains that: -
 It is essential to realize that sorting need be performed of the size of the sub array is 0 and
1. Therefore, nothing is needed to be done.
 Otherwise, to sort the subarray, merge type utilizes divide-and-conquer.
To combine the sorted sub-arrays array [p. q] and array [q+1.. r], use merge (array, p, q, r).
Uncomment the Program.assertEqual function at the bottom once implemented to verify the
passing of the test assertion.
Important characteristics
 In order to sort linked lists, Merge Sort is helpful.

 Merge Sort is a stable sort, meaning that the same component in an array maintains its
initial positions in relation to each other.
 Merge sort overall time complexity is O(nLogn). It is more efficient because the runtime
is also O(nlogn).
 In the worst case, the space complexity of the Merge sort is O(n). This implies that for
the last information sets this algorithm requires a lot of room and can slow down
activities.
As multilevel memory hierarchies are used, location of reference can be of paramount
significance in software optimization on contemporary pcs. Cache-aware versions of the merge
sort algorithm were proposed, whose operations were specifically selected to minimize the
movement of pages to and from the memory cache of a machine. For example, when subarrays
of size S are reached, the tiled merge sort algorithm stops dividing the subarrays, where S is the
number of data items that fit into the cache of a CPU. Each of these subarrays is sorted with an
in-place sorting algorithm, such as the type of insertion, to discourage memory swaps, and then
the normal sort of merge is completed in the standard recursive mode. This algorithm has shown
better performance on computers benefiting from cache optimization. It is proposed an
alternative type of merge using continuous extra room. This algorithm was subsequently refined.
Many internal sorting apps also use a type of parallel sorting where the input is divided up to a
greater amount of sub lists, ideally a number for which merging still makes the presently
processed collection of websites fit in the primary memory.
Merge sort and other sorting techniques
While heapsort has the same time boundaries as merge sort, it requires only 1 auxiliary space
instead of the n merge type. Effective quicksort implementations usually outperform merge sort
on typical contemporary architectures to sort RAM-based arrays. On the other side, merge sort is
a stable type and is more effective in managing slow sequential media access. Merge sort is often
used in linked list and is said to be the best option for it: in this scenario, a merge sort is
comparatively simple to execute in such a manner that it needs only some (1) additional room,
and the slow random-access performance of a linked list makes some other algorithms (such as
quicksort) perform badly and others (such as heapsort) impossible. The array is divided into only

2 halves (i.e. n/2) in the merge type. Whereas the array is divided into any proportion in the
event of a quick sort. There is no compulsion to quickly split the range of components into equal
components. Merge sort is able to work with any type of data set which is available without
having any constraint on the size of the data set, whereas on the other hand quick sort cannot
work with large amount data sets
Examples of merge Sort program in Java
Merge sort is the sorting technique that follows the approach of dividing and then conquering.
For instance, think of an Array called A having n number of elements in it. The algorithm of this
sorting theme would be processing the elements in the following 3 steps.
 If it is found out that the array A contains 0 or only 1 element, then it is already said to be
sorted in the given order. If it is not sorted then it would divide the array into two sub
arrays of equal parts.
 The conquering part involves sorting the two arrays so made in the previous step by the
help of merge sort.
 Finally, all the sub arrays are merged into a single and final file which is sorted in the
given manner and thereby maintaining the order of the given array elements.

Algorithm:

Program: