We will understand the algorithm and the working principle using a few program examples. In Merge Sort, a sequence of elements are divided into two smaller parts and are individually sorted and then merged eventually into one sorted list. We will look into the points below to understand the merge sort in detail. The concept involved in Merge Sort is quite simple as we have learnt the divide and conquer strategy in the previous section.
It follows the technique of dividing, then solving, and then merging the solution to obtain a sorted list of elements. We will look into the illustrated diagram and example to understand the concept behind Merge Sort in details. Now that we are familiar with the concept of Merge Sort , we can now develop an algorithm of Merge Sort before we put it into implementation.
The working of the Merge Sort in accordance to the above Algortihm is as follows:. We will look into an illustrated diagram example to understand the working of Merge Sort step by step. Now that we understand the concept of Merge Sort and also we have written the algorithm of Merge Sort, now we can implement Merge Sort in a programming language to perform the operation.
In the next section of the tutorial, we will discuss the Quick Sort in Data Structure and its concept and the algorithm of Quick Sort for performing different sorting operations in detail. We shall discuss the algorithm and working principle in the same way as done in this article using real-world examples.
Explanation: First, we have algorithm MERGE-SORT that takes an array as an argument and sees if the last index is greater than the left index to see if the array contains some elements to be sorted. Then a middle point m is calculated to divide the array into 2 sub-arrays, and the same algorithm is called for those sub-arrays. When recursive calls end and we end up having single elements in each sub-array, the MERGE algorithm is called. This algorithm declares 2 arrays LArray and RArray to hold the elements in 2 sub-arrays.
Then, elements in the 2 sub-arrays are compared simultaneously, and Array A is populated with elements in the sorted arrays. This algorithm is preferred over quick sort while working with the linked list as in quicksort, and there was a need to access the elements a lot which is of O n complexity in case of the linked list. In the above picture, elements of the array are sorted using Merge sort.
Also, we can see the sequence or the order in which the elements are processed. As it is a recursive algorithm, its time complexity can be expressed as a recurrence relation.
Here are the 3 types of time complexity which are explained below:. Worst Case: The case when all the array elements are sorted in the reverse order. Average Case: This is the case when the elements are partially sorted. And Complexity of Merge algorithm is O n in all cases.
Thus Merge sort is a stable algorithm that uses O n of auxiliary space and Divides and Conquer paradigm to sort the list of elements. We see that 14 and 33 are in sorted positions. We compare 27 and 10 and in the target list of 2 values we put 10 first, followed by We change the order of 19 and 35 whereas 42 and 44 are placed sequentially.
In the next iteration of the combining phase, we compare lists of two data values, and merge them into a list of found data values placing all in a sorted order. Merge sort keeps on dividing the list into equal halves until it can no more be divided. By definition, if it is only one element in the list, it is sorted. Then, merge sort combines the smaller sorted lists keeping the new list sorted too.
We shall now see the pseudocodes for merge sort functions. To know about merge sort implementation in C programming language, please click here.
0コメント