Merge Sort and Insertion Sort

 

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

2. Merge sublists repeatedly to create newly ordered sublists until only one sublist remains. The ordered list will be shown below.

 

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)

2. In the second iteration merge the above arrays of size 2

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.