In this article we will learn about merge sort. Merge sort is one of the sorting technique that follows divide and conquer strategy to sort the elements.
In merge sort algorithm we split the entire array into two equal parts, the sub- arrays are again continuously divided into parts until the array can not be divided further. Then we will combine the sub-arrays by sorting them.
Let’s understand the merge sort by an example:
Let’s take an unsorted array.
As per merge sort divide the array into two parts
Again divide all these sub arrays into two parts until the sub-arrays can not be divided further:
The sub-arrays can not be divide further. Now combine the sub-arrays by comparing the elements of each array. We take first two arrays compare the elements, sort them accordingly and then merge them into a single array. Again we will take other two arrays compare the elements, sort them and then merge them into a single sorted array and so on.
So, in this way we will sort the entire array.