Merge Sort
The Merge Sort algorithm is a sorting algorithm that is based on the Divide and Conquers paradigm. In this algorithm, the array is initially divided into two equal halves and then they are combined in a sorted manner.
Let’s see how Merge Sort uses Divide and Conquer:
The merge sort algorithm is an implementation of the divide and conquers technique. Thus, it gets completed in three steps:
- Divide: In this step, the array/list divides itself recursively into sub-arrays until the base case is reached.
- Conquer: Here, the sub-arrays are sorted using recursion.
- Combine: This step makes use of the merge( ) function to combine the sub-arrays into the final sorted array.
Working of Merge Sort algorithm:
To know the functioning of merge sort, lets consider an array arr[] = {38, 27, 43, 3, 9, 82, 10}
At first, check if the left index of array is less than the right index, if yes then calculate its mid point
Now, as we already know that merge sort first divides the whole array iteratively into equal halves, unless the atomic values are achieved.
Here, we see that an array of 7 items is divided into two arrays of size 4 and 3 respectively.
Now, again find that is left index is less than the right index for both arrays, if found yes, then again calculate mid points for both the arrays.
Now, further divide these two arrays into further halves, until the atomic units of the array is reached and further division is not possible.
After dividing the array into smallest units, start merging the elements again based on comparison of size of elements
Firstly, compare the element for each list and then combine them into another list in a sorted manner.
After the final merging, the list looks like this:
Introduction to Sorting Techniques – Data Structure and Algorithm Tutorials
Sorting refers to rearrangement of a given array or list of elements according to a comparison operator on the elements. The comparison operator is used to decide the new order of elements in the respective data structure.
When we have a large amount of data, it can be difficult to deal with it, especially when it is arranged randomly. When this happens, sorting that data becomes crucial. It is necessary to sort data in order to make searching easier.
Contact Us