**MERGE
SORT**

One
of the most effective sorting algorithms is merge sort. The merge sort also
follows divide and conquer approach as in the case of QuickSort. It splits the
input array in half, calls itself for each half, and then combines the two
sorted sections. If we want to merge an array of ‘n’ elements, we will first
split that array into two. Consider the array A[n], the split is done as
A[1...(n/2)] and A[(n/2)....n]. Then again splits these arrays until it reaches
a single element. Then sort the two sub arrays and merges it using a function. Merge
sort continuously cuts down a list into several sublists until each sublist
contains just one variable, then merges those sublists into a sorted list.

**Working
of Merge Sort**

**Top-down
attempt**

The
recursion mechanism is used in the top-down merge sort technique. It starts at
the top and works its way down, with each sequential turn saying the same
thing, such as “What is needed to sort the array?” and the solution being
“split the array into two, make a recursive call, and combine the results.”

Consider
the below given situation

1.
Separate the unsorted collection into n sublists, each with one variable (a
list of 1 element is supposed sorted).

The merging is done in the following manner

Both lists' first item is compared. As two elements are ordered in ascending order, the smaller of the two becomes a new element in the sorted list. Finally all the sublist will be vacant and the merged list will contain all the elements that contained in the sublist earlier.

**Bottom-Up
approach in merge sort operation**

Iterative technique is used in the Bottom-Up merge sort strategy. It begins with a “single-element” sequence and then blends two adjacent elements while still sorting them. The combined-sorted arrays are combined and sorted again until only one single unit of sorted array remains.

1.
Combine two arrays of the same dimension (Iteration 1)

3.
3^{rd} iteration

Finally
we get the sorted list.

**INSERTION
SORT**

In
this mechanism one element is considered at a time and sort it in its correct
position. The array elements are sequentially compared and then placed in a
certain order simultaneously. The example can be seen in the way a deck of
cards is organised. The name Insertion Sort comes from the fact that it
operates by adding an entity at a specific location.

**Working
of Insertion Sort**

■ The first step is to compare the element in
question to its neighbouring element.

■ For each analysis shows that the element in
question may be inserted in a specific location, space is generated for it by
moving the other elements one place to the right and placing the element in the
proper location.

■ The operation is repeated until all of the
array's elements are in their proper positions.

It
iterates through the input elements, growing the sorted array each time. It
compares the current variable to the sorted array's largest value. If the
current element is larger, it remains in place and goes on to the next element;
otherwise, it locates the element's right location in the sorted list and moves
it there.

Consider the array A=[7, 4, 5, 2]

Since
7 is the first entity, there is no other element with which it can be compared,
it remains in its original place. Now, as we get closer to 4, the largest
factor in the sorted list is 7, which is greater than 4. As a result, shift 4
to its proper location, which is before 7. Similarly, we can shift 5 to its
proper location since 7 (the largest factor in the sorted list) is greater than
5. Finally, since all of the elements on the left side of 2 (sorted list) are
greater than 2, all of the elements on the left side of 2 are pushed one step
ahead, and 2 is put in the first position. Finally, a sorted array will be
generated from the specified array.

## 0 on: "Merge Sort and Insertion Sort"